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是偶数。
如果一个数能够被它之前的质数整除,那么这个数不是质数。