趣味的数

趣味的数

（1）素数

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

一，定义法

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

#include<stdio.h>
//判断n是不是素数，是返回true,否则返回false;
bool is_prime(int n)
{
     inti = 0;
     if(n==0 || n==1)
     {
         returntrue;
     }
     for(i=2; i<n; i++)
     {
         if(n%i == 0)
         {
              returnfalse;
         }
     }
     returntrue;
 
}
int main()
{
     intn = 0;
     while(scanf("%d",&n)!=EOF)
     {
         if(is_prime(n))
         {
              printf("%dis prime.\n",n);
         }
         else
         {
              printf("%dis not prime.\n",n);
         }
     }
     return0;
}

二 优化一

我们思考这么一个问题，一个数n的最大的约数和最小的约数分别是什么？很明显就是1和n(也就是他自己本身)。其实在看看素数的定义我们会发现其实素数就是只有两个约数的数，而任何一个数至少有两个约数（它们分别是1和它本身），也就是一个数的最大约数和最小约数对吧。那么我们想象一个数的次（第二）大约数和次小约数是什么呢？ok，有一个很明显那就是次小约数是2（当然1和0这两个特殊情况不在我们考虑范围之内），但是次大约数好像就不是那么明显了，这是为什么呢？其实因为我们每一个数不一定能被2整除，那么自然这个次大约数就不知道了，但是我们可以得出下面这个结论：

任何数n的次大约数小于或等于n/2。

那么我们可以利用这个结论让我is_prime(int n)函数运算的得快一倍，在上面这个函数我们枚举了（2～n-1）,而现在我们只需要枚举(2~n/2)了。是不是快了一倍啊。代码实现很简单如下：

//判断n是不是素数，是返回true,否则返回false;
bool is_prime(int n)
{
     inti = 0;
     if(n==0 || n==1)
     {
         returntrue;
     }
     for(i=2; i<=n/2; i++)
     {
         if(n%i == 0)
         {
              returnfalse;
         }
     }
     return true;
}

三优化二

其实还有这么一个规律：任何数n的约数都有大约数集和小约数集之分。我们加入数n存在约数1那么n/1=n,n也是n的约数。其实很明显任何一个数的约数都是成对的。如：12有（3-4）这个约数对（因为3×4=12），当然向3*3=9这种特殊情况除外，我们称约数对中小的那个数叫小约数，包含所有小约数的集合叫小约数集，约数对中大的数大约数，包含所有大约数的集合大小约数集。其中小约数集中最大的约数我们叫最小最大约数。那么12有约数对（1-12）,(2-6),(3-4)。其中小约数集为1，2，3。而大约数集为4，6，12. 12的最小最大约数是3. 这样我们会发现下面这条规律：

任何数n(除了能开2次方的数)的约数都是成对出现的。且任何数(包括能开2次方的数)的最小最大约数小于或等于i（其中i满足i*i=n）

那么我们可以进一步减少枚举的数的个数，代码实现如下：

//判断n是不是素数，是返回true,否则返回false;
bool is_prime(int n)
{
     int i = 0;
     if (n==1 || n==0)
     {
         return true;
     }
     for (i=2; i*i<=n; i++)
     {
         if (n%i == 0)
         {
              return false;
         }
     }
     return true;
}

四优化三

当然还有其他的素数的测试方法，有点难，要用到很强的数论知识，不好证明。在此省略，有兴趣的同学可以参考其他资料。其中《算法导论》数论那一章就详细的介绍了。网上也有 不少好的博客哦，下面是

techq's blog的博客大素数测试http://blog.csdn.net/techq/article/details/6125696写得不错可以参考下下。

（2）最大公约数

本节默认讨论的都是非负整数集的最大公约数。最大公约数的定义就省略了。下面介绍：

ＧＣＤ递归定理：

ｇｃｄ（ａ，ｂ）＝ｇｃｄ（ｂ，ａ％ｂ）。ｇｃｄ（ａ，ｂ）就是ａ，ｂ最大公约数。

l       欧几里得算法
int gcd(int a,int b)
{
     if(b == 0)
     {
         returna;
     }
     returngcd(b, a%b);
}

简单吧！

->课后思考？？？

我们都知道递归会消耗更多系统资源，甚至可能造成栈溢出。综合考虑我们还是决定将上面递归式给成迭代，这个任务就叫给你了？？？？？

二 欧几里得算法推广

我们推广欧几里德算法计算满足下列条件的整数系ｘ和ｙ：ｄ＝ｇｃｄ（ａ，ｂ）＝ａｘ＋ｂｙ。

下面是该算法的伪代码：

ｇｃｄ＿ｅｘｔｅｎｄ（ａ，ｂ）

１，ｉｆ　ｂ＝０

２，　　　　ｔｈｅｎ　ｒｅｔｕｒｎ　（ａ，１，０）

３，（ｄ＇，ｘ＇，ｙ＇）＜－ｇｃｄ＿ｅｘｔｅｎｄ（ｂ，ａ％ｂ）

４，（ｄ，ｘ，ｙ）＜－（ｄ＇，ｙ＇，ｘ＇－ａ／ｂ*y＇）

５，return(d, x, y)

C语言实现：

struct Node{
     intd;
     intx;
     inty;
};
struct Node gcd_extend(int a,int b)
{
     structNode node,temp;
     if(b == 0)
     {
         node.d= a;
         node.x= 1;
         node.y= 0;
         returnnode;
     }
     temp= gcd_extend(b, a%b);
     node.d= temp.d;
     node.x= temp.y;
     node.y= temp.x-a/b*temp.y;
 
     returnnode;
}

->课后思考？？？

题目内容：

求一堆数的最大公约数

输入描述：

先输入m，代表测试数据的组数。在每一组先输入n（n<=100），表示这次要求的这堆数的个数，后面跟着n个数，n都为正整数。

输出描述：

输出他们的最大公约数。

输入样例：

3

2 1 2

3 1 2 3

6 4 2 8 12 24 68

输出样例：

1

1

2

解题策略：

我们只要明白下面这个简单的例子就可以了，看看这个定理gcd(a,b,c)=gcd(gcd(a,b),c)。思考一下！！！是不是对的？有了它无论我们求多少个数的最大公约数，我们都能求出来了。

C++实现如下：

#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;
}

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

参考书目《算法导论》