通过编程找到一定范围内的素数（求小于n的最大素数问题）

火客 2023-05-31 02:28:05 294

通过编程找到一定范围内的素数（求小于n的最大素数问题）如某一个数是否是素数的问题，只有奇数才可能是素数，偶数不是素数。1.2 减少搜索空间用枚举法，简单枚举就是将全部可能一一枚举，但枚举也是可以优化的。1.1 解空间确定，建立简洁的数学模型模型中变量数尽可能少，它们之间相互独立。

素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2~16的任一整数整除。

求小于n的最大素数问题。

需要分治：

1 先是求某一个数是否是素数

用枚举法，简单枚举就是将全部可能一一枚举，但枚举也是可以优化的。

1.1 解空间确定，建立简洁的数学模型

模型中变量数尽可能少，它们之间相互独立。

1.2 减少搜索空间

如某一个数是否是素数的问题，只有奇数才可能是素数，偶数不是素数。

通过编程找到一定范围内的素数（求小于n的最大素数问题）(1)

设a * b = n，i * i = n，若a<=i，则必有b>=i 。如8*8=64，则a如果是2、4、8，则b就是32、16、8，反过来也是如此，因此只需判定在2~√64之间有无因子即可。

1.3 合适的搜索顺序

搜索空间的遍历顺序要与模型中条件表达式一致。

2 找某一区间的最大素数

同样需要考虑解空间、搜索空间与顺序。

以下是不同策略的简单测试代码：

#include <iostream> #include <cmath> #include <ctime> using namespace std; bool isPrime(int n) { if(n==2) return true; if(n%2==0) return false; for(int i=3;i<=sqrt(n);i =2) { if(n%i==0) return false; } return true; } bool isPrime(int n int start) { if(n==2) return true; if(n%2==0) return false; for(int i=start;i<=sqrt(n);i =2) { if(n%i==0) return false; } return true; } int maxPrime1(int n) { int max=2; for(int i=2;i<=n;i ) { if(isPrime(i) && max<i) max=i; } return max; } int maxPrime2(int n) { for(int i=n;i>2;i--) { if(isPrime(i)) break; } return i; } int maxPrime3(int n) { int max=2; for(int i=2;i<=n;i ) { if(isPrime(i max) && max<i) max=i; } return max; } typedef int (*PF)(int); void test(PF pf int n) { clock_t start = clock(); cout<<pf(n)<<endl; cout<<"time consumed: "<<clock()-start<<endl; } int main() { int n=1234567; test(maxPrime1 n); test(maxPrime2 n); test(maxPrime3 n); cin.get(); return 0; } /* 1234547 time consumed: 3198 1234547 time consumed: 0 1234567 time consumed: 93 */

1640年6月，法国数学家费马在给梅森（Marin Mersenne）的一封信中写道:“在艰深的数论研究中，我发现了三个非常重要的性质。我自信它们将成为今后解决素数问题的基础。”这封信讨论了2^p-1的数。

数2^p-1最早出现在欧几里得《几何原本》(公元前300年左右)第九章命题6中。他发现这种类型的素数和完全数之间有着密切如果2^p－1是素数，则2^(p－1)(2^p－1) 是完全数。

例如p=5，是一个质数，2^p-1=31也是质数，（2^p-1）X2^（p-1）=31X16=496是完全数（1 2 4 8 16 31 62 124 248）。

梅森以此作为基础，花4年时间研究，并于1644年在他的《物理数学随感》一书中写道:“总结前人的工作和我个人的研究，可以得到结论：在p小于或等于257的数中，仅当p=2、3、5、7、13、17、19时，2^p-1是素数外，并猜想p=31、67、127和257时，2^p-1是素数；对于p<257的其它数值，2^p-1都是合数。”

后来人们才知道梅森的断言其实包含着若干错漏。不过梅森的工作却极大地激发了人们研究2^p-1型素数的热情，使其摆脱作为 “完全数” 的附庸地位，可以说梅森的工作是2^p-1型素数研究的一个转折点和里程碑。由于梅森学识渊博、才华横溢、为人热情以及最早系统而深入地研究2^p-1型的数，为了纪念他，数学界就把这种数称为 “梅森数”，并以Mp记之（其中M为梅森姓名的首字母），即Mp=2^p-1。如果梅森数为素数，则称之为 “梅森素数”（即2^p-1型素数，
Mersenne prime）。

长期以来人们一直以为所有2^p－1型的数可能都是素数，但雷吉乌斯在1536年纠正了这一错误观点。他指出2^11-1=23×89=2047，并不是素数。由此人们开始深入思考哪些2^p－1型的数才是素数？这样的素数又有多少？

1930年在美国数学协会的年会上，数学家科尔在黑板上算出了2^67-1=193707721×761838257287，发现了梅森的纰漏。

19世纪70年代，法国数学家爱德华·卢卡斯（1842～1891）提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理，为梅森素数的寻找提供了有力的工具。 1876年，卢卡斯证明M127确实也是素数，这是人们靠手工计算发现的最大梅森素数，长达39位。

在手工计算的漫长年代里，人们历尽艰辛，一共只找到12个梅森素数。

通过编程找到一定范围内的素数（求小于n的最大素数问题）(2)