笔试题-求小于等于N的数中有多少组素勾股数

题目描述：

一组勾股数满足：a²+b²=c²；

素勾股数：a，b，c彼此互质。

输入正整数N；

输出小于等于N的数中有多少组勾股数。

例：

输入：10

输出：1

思路：我是直接暴力破解的……

首先找出勾股数，再判断是不是素勾股数。（如果N较大，注意定义成int可能超范围，当然N很大时就不能用暴力破解法了……）

代码：

#include <vector>

#include <iostream>

using namespace std;

bool isr(int a, int b);

int main()

{

    int N;

    cin>>N;//输入N;

    int res=;

    long long a,b,c;

    for(a=;a<=N;a++)

    {

        for (b=a+;b<=N;b++)

        {

            for (c=b+;c<=N;c++)

            {

                if (a*a+b*b==c*c)

                {

                    if (isr(a,b)&&isr(a,c)&&isr(b,c))

                    {

                        res++;

                    }

                }

            }

        }

    }

    cout<<res<<endl;

    system("pause");

    return ;

}

bool isr(int a, int b)//判断两个数是否互质;

{

    if (a==b)

    {

        return false;

    }

    else if (a==||b==)

    {

        return true;

    }

    else

    {

        while()

        {

            int t=a%b;

            if (t==)

            {

                break;

            }

            else

            {

                a=b;

                b=t;

            }

        }

        if (b>)

        {

            return false;

        }

        else

        {

            return true;

        }

    }

}

补充知识点：只有1为公约数的两个正整数才互质，即两个正整数最大公约数是1，即可判断他们互质。

巴特西

笔试题-求小于等于N的数中有多少组素勾股数

最新文章

热门文章