编程计算1到n之间的素数的个数（求小于n的最大素数问题）

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

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

需要分治：

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

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

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

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

1.2 减少搜索空间

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

设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个梅森素数。

2300多年来，人类仅发现51个梅森素数，由于这种素数珍奇而迷人，因此被人们誉为 “数海明珠” 。自梅森提出其断言后，人们发现的已知最大素数几乎都是梅森素数，因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。

目前仅发现51个梅森素数，最大的是M82589933（即2的82589933次方减1），有24862048位。

用因式分解法可以证明，若2^n－1是素数，则指数n也是素数；反之，当n是素数时，2^n－1（即Mp）却未必是素数。

ref

https://www.codeproject.com/Articles/429694/Finding-prime-numbers

－End－