转载请注明出处: http://www.liubida.com/programming_language/prime/
什么是质数？
1. 大于1的正整数
2. 只能被1和自己整除
满足1和2的就是一个质数（也叫素数），反之被叫做合数。
质数相关的东西
数学上，任何一个整数均可表示为质数的乘积，所以质数在数学上很重要。虽然从质数中很难得到一些定理。
公元前3世纪，古希腊数学家欧几里德证明了质数的数目是无穷的。而最近几年，由陶哲轩和格林证明了“存在任意长度的质数等差数列”这一重要命题。我不打算就这些个数学证明写点什么，就简单的就这个命题举一些例子吧。
命题：存在任意长度的质数等差数列，它的意思：能够找到一个由质数构成的等差数列，其长度为指定的L。
比如，长度为5的质数等差数列：5，17，29，41，53；
长度为10的质数等差数列：199，409，619，829，1039，1249，1459，1669，1879，2089；
到目前为止，已知的质数等差数列的长度为23，其数列的第一个数是56211383760397，间隔常数为44546738095860。
对于一个随机的正整数n来说，它有50%的几率能被2整除，33%的几率能被3整除。可以计算出，n有88%的几率能够被100以内的某个数整除，有92%的几率能够被1000以内的某个数整除。基于这些分析，关于质数分布的事实是：随着正整数数值的增加，质数的分布变得越来越稀疏。
那么，我们的问题是？
如何判断正整数n是否为一个质数？
请列出1000，10000以内的质数？
现在求质数的方法有很多，wiki上列举了AKS/Elliptic curve/Miller-Rabin/Solovay-Strassen/Fermat等这些专业方法。但是我们平时用的一般是尝试相除法和筛选法。
尝试相除法–Trial division
算法描述：对于给定的正整数n，依次从集合[2...n-1]中取数，如果存在m使得n能被m整除，那么n就不是质数，反之n为质数。
java代码：
boolean IsPrime1(int n) {
if (n <= 1)
return false;
for (int i = 2; i < n-1 ; i++) {
if (n % i == 0)
return false;
}
return true;
}
这种方法有一个优化。
注意到当n>2时,n-1肯定不能被n整除,所以循环边界设定在i<n-1,对这一点我们多想几步.
当n=4时，n-1不能被整除;
当n=5时，n-1,n-2,n-3不能被整除;
当n=10时，n-1,n-2,n-3,n-4,n-5等不能被整除;
当n=100时，n-1,n-2,n-3,n-4,n-5,n-5等不能被整除;
可以发现,其实有很多m是没有必要的,比如n=100时,51~99的数都没法被其整除,
那么对这些除数的判定是否有更简单的方法呢?
我们假设存在正整数p和q,它们使得n=pq成立.
p=1,q=n;//其中的一个解
p=√n,q=√n; //考虑n是一个平方数,则存在这样一对解
p=n,q=1;//随着p逐渐增大,对应的q必须逐渐的减小,才能使得等式可能成立,直到得到最后的一个解.
通过分析得出,p是在逐渐增大,q是在逐渐减小.那么实际上,我们只需判定[2,√n]区间的数能否被整除就可以了.
假设,p=√n+r能被整除,则对应q则必定小于√n,则在对[2,√n]区间内进行判定时就能找出一对解.
所以,除数的判定区间可以缩小到[2,√n].
算法描述: 对于给定的正整数n，依次从集合[2,√n]中取数，如果存在m使得n能被m整除，那么n就不是质数，反之n为质数。
java代码:
boolean IsPrime2(int n) {
if (n <= 1) return false;
int b = (int) Math.sqrt(n);
for (int i = 2; i <= b; i++) {
if (n % i == 0) return false;
}
return true;
}
筛选法–Sieve of Eratosthenes
In mathematics, the Sieve of Eratosthenes ancient algorithm for finding all prime numbers up to a specified integer. It works efficiently for the smaller primes (below 10 million). It was created by Eratosthenes, an ancient Greek mathematician. However, none of his mathematical works survived—the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.
–摘自wiki: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
筛选法说起来还是比较简单的,它的具体过程可以看图
目的:列出<=n的所有质数
算法描述:
1. 创建一个从2到n的顺序列表List:[2,3,4,...,n]
2. 2是第一个质数,初始时让p=2
3. 从p开始,在List中标记出p的倍数(2倍开始,2p,3p,4p…)
4. 找出List中p之后的没有被标记的那个数,将其值赋给p
5. 重复步骤3,步骤4,直到List中p之后的所有数都被标记
6. List中未被标记的数就是质数
java代码:
static void ListPrime2(int n) {
/**
* 标记0为质数,1为合数
*/
int[] primeList = new int[n + 1];
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
// 加法版
int j = i + i;
while (j <= n) {
primeList[j] = 1;
j = j + i;
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
// System.out.print(i + " ");
ret.add(i);
}
}
}
对于这个算法有几点可以优化:
a. step3: 开始比较p的倍数可以从p^2开始标记. 因为p*(p-1),p*(p-2),p*(p-3),…这些已经在前面被(p-i)标记过了,即p^2之前的都已经被判定标记过了.
b. step5: 由上面可知,p^2之前的都已经被判定标记过,则当p^2>=n时,说明n之前的都被判定标记过,筛选结束.
c. 当p=2时,所有的偶数都会被标记;则当p>2时,p的偶数倍可以直接被忽略(已经被p=2标记过).p=1p,每次标记的步长为2p, 则标记的index依次为1p,3p,5p,…
java代码:
static void ListPrime3(int n) {
/**
* 标记0为质数,1为合数
*/
int[] primeList = new int[n + 1];
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
int j = i * i; //从p^2开始标记
if (j > n) break; //如果p^2>n,则列表中的数已经被标记完
if (i > 2) {
//当p>2时,步长为2p
while (j <= n) {
primeList[j] = 1;
j = j + i + i;
}
} else {
while (j <= n) {
primeList[j] = 1;
j = j + i;
}
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
// System.out.print(i + " ");
ret.add(i);
}
}
}
结合前面的根号n(只筛选根号n之前的数), 下面的应该更快!
经过实际测试,Prime4和Prime3其实差不多…为什么呢?因为if (j > n) break;这一句使两者的实际循环次数一样
java代码:
static void ListPrime4(int n) {
/**
* 标记0为质数,1为合数
*/
int[] primeList = new int[n + 1];
int sqrt = (int)Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (primeList[i] == 0) {
int j = i * i; //从p^2开始标记
//if (j > n) break; //如果p^2>n,则列表中的数已经被标记完
if (i > 2) {
//当p>2时,步长为2p
while (j <= n) {
primeList[j] = 1;
j = j + i + i;
}
} else {
while (j <= n) {
primeList[j] = 1;
j = j + i;
}
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
// System.out.print(i + " ");
ret.add(i);
}
}
}
wiki链接：
http://en.wikipedia.org/wiki/Prime_number
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
今天小猪跑来要和我比.虽然败了但是他用了个讨巧的方法, 我也借鉴来. 果然快了许多. 2000w 668ms 
Java代码:
static void ListPrime(int n) {
/**
* false为质数,true为合数
*/
boolean[] primeList = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
if (!primeList[i]) {
int j = i * i;
if (j > n)
break;
if (i > 2) {
while (j <= n) {
primeList[j] = true;
j = j + i + i;
}
} else {
while (j <= n) {
primeList[j] = true;
j = j + i;
}
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
ret.add(2);
for (int i = 3; i <= n;) {
if (!primeList[i]) {
//System.out.print(i + " ");
ret.add(i);
}
i += 2;
}
}