Java实现求小于n的质数的3种方法
质数概念
质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。
一：根据定义去求解：
也是最笨的方式，效率比较低：
packagetest.ms;
publicclassFindPrime{
//findtheprimebetween1to1000;
publicstaticvoidmain(String[]args){
printPrime(1000);
}
publicstaticvoidprintPrime(intn){
for(inti=2;i<n;i++){
intcount=0;
for(intj=2;j<=i;j++){
if(i%j==0){
count++;
}
if(j==i&count==1){
System.out.print(i+"");
}
if(count>1){
break;
}
}
}
}
}
2：平方根：
packagetest.ms;
publicclassPrime{
publicstaticvoidmain(String[]args){
for(intj=2;j<1000;j++){
if(m(j)){
System.out.print(j+"");
}
}
}
publicstaticbooleanm(intnum){
for(intj=2;j<=Math.sqrt(num);j++){
if(num%j==0){
returnfalse;
}
}
returntrue;
}
}
3：找规律（摘自一个论坛讨论）
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。
packagetest.ms;
importjava.util.ArrayList;
importjava.util.List;
publicclassPrimes{
publicstaticvoidmain(String[]args){
//求素数
List<Integer>primes=getPrimes(1000);
//输出结果
for(inti=0;i<primes.size();i++){
Integerprime=primes.get(i);
System.out.printf("%8d",prime);
if(i%10==9){
System.out.println();
}
}
}
/**
*求n以内的所有素数
*
*@paramn范围
*
*@returnn以内的所有素数
*/
privatestaticList<Integer>getPrimes(intn){
List<Integer>result=newArrayList<Integer>();
result.add(2);
for(inti=3;i<=n;i+=2){
if(!divisible(i,result)){
result.add(i);
}
}
returnresult;
}
/**
*判断n是否能被整除
*
*@paramn要判断的数字
*@paramprimes包含素数的列表
*
*@return如果n能被primes中任何一个整除，则返回true。
*/
privatestaticbooleandivisible(intn,List<Integer>primes){
for(Integerprime:primes){
if(n%prime==0){
returntrue;
}
}
returnfalse;
}
}
第一种和第二种都是很简单的方法：
第三种方法说明了一个质数的特性：在所有质数中，只有2是偶数。
如果一个数能够被它之前的质数整除，那么这个数不是质数。