为。令,则不被中任何一个整除。因而,要么是素数,要么有比大的素因子,这与为最大素数相矛盾。关于素数的下一个基本问题是:如何求出小于某一给定整数的所有素数?Eratosthenes筛法求素数古希腊的另一位学者Eratosthenes给出了解决这一问题的方法,这一方法被后人称为Eratosthenes筛法。Eratosthenes筛法的基本思想是,将自然数列从2开始按顺序排列至某一整数。首先,从上述数列中划去所有2的倍数(不包括2)。在剩下的数中,除2外最小的是3。接着,从数列中划去3的倍数(不包括3)。然后在剩下的数中,再划去5的倍数……。这个过程一直进行下去,则最后剩下的数就是不超过的所有素数。下面我们就利用筛法通过编程实现求某个数的所有素数。利用Eratosthenes筛法,通过计算机编程求100,500,1000,1500的所有素数,运行过程如下:2.利用试除法求素数筛法是用乘法寻找素数,实际上,也可以用试除法判断一个数是否是素数。而且,用试除法的效率可能会更高。假设我们已经找到了前n个素数,为了寻找下一个素数,我们从开始依次检验每一个整数,看是否能被某个整除。如果能被前面的某个素数整除,则为合数。否则即为下一个素数。实际上,为了提高算法的效率,我们不需要用前面的每一个素数去试除,而只需用不超过的素数去除就可以了。下面我们运用试除法来求100,500,1000所有的素数,程序运行如下:从以上的运行过程可以看出,试除法求素数比Eratosthenes筛法更快。3.数素性的判别数素性的判别方法有三种,即:1)n-1检验法2)基于广义黎曼猜想的判别法3)概率判别法,下面我们利用概率判别法对这些数进行数素性判别,程序运行如下:由此,我们可以看到对一个数的数素性判别有好多方法。素数在我们学习的数中扮演着很重要的角色,所以判断一个数是否是素数是非常有用的。实验结果和结果分析:附录:
全文预览
