求质数

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。1和0既非素数也非合数。

 

求质数的算法

 

算法1、计算n除以2到根号n最接近的整数，如果都不能整除，n就是质数。
     比如101，要除以2，3,4,5直到10，如果都不能整除，就是质数。
     原理解释 ： 设N=pq，若p>根N，那么q<根N
     所以只要N不被　2~根N　之间的整数整除，它一定不能被　根N~N-1　之间的整数整除，那它一定是素数。
     (^_^)

 

算法2、基本原理就是判断整除，用一个ArrayList记录已知的质数，一开始放入2，然后从3开始对奇数进行 for(int n=3; ;n+=2)循环，对每个待判断的n，用已知的质数依次判断是否能整除，如果得到一个新的质数， 就把它放到ArrayList中。