生趣的数

趣味的数

    趣味的数

（1）  素数

素数的定义：只能被1和自己本身整除的数叫素数。那么应该如何判断一个数n(n为正整数)是否为素数呢？

一， 定义法

既然只能被被自己和本身整除那么我们就用枚举，让数n除以2到n-1若有一次可以被整除，显然违反了素数的定义。反之则为素数。代码实现如下：

#include<iostream>using namespace std;const int N = 100;//求a,b的最大公约数int gcd(int a, int b){     if(b == 0)     {         returna;     }     returngcd(b, a%b);}int main(){     inta[N];     inti =0,j = 0;     intm,n;     cin>>m;     while(i<m)     {         cin>>n;         j= 0;         while(j<n)         {              cin>>a[j];              ++j;         }          int gc = gcd(a[0],a[1]);         j= 2;         while(j<n)         {              gc= gcd(gc, a[j]);              ++j;         }         cout<<gc<<endl;         ++i;     }     return0;}

当然问题也就来，你觉得上面的方法可以优化吗？或者你有更好的想法？？？？

参考书目《算法导论》