【计蒜客】素数个数

xiaoxiao2021-02-28  10

用 0,1,2,3 \cdots 70,1,2,37 这 88 个数组成的所有整数中,质数有多少个(每个数字必须用到且只能用一次)。

提示:以 0 开始的数字是非法数字

可以发现 5、7、11、13、17、19、23、29、31、37、41、43

只要数字大于5,这些素数就会出现6*x+1或是6*x-1的周围。所以只要是大于5的数字,要是素数就应该在6的倍数周围。

但是在6周围的不都是素数,所以在程序中还得进行判断。

对一个数进行因数分解,可以发现 其中的一个数肯定是小于sqrt(n)的。

public class Test2 { int array[]=new int[8]; int box[]=new int[8]; int zhishu; public void sort(int step){ if(step==8){ int sum = 0; if(box[0]==0) return; for(int i=0;i<8;i++){ sum+=box[i]*(int) Math.pow(10.0, (7.0-i)); } if(isZhiShu(sum)) zhishu++; return; } for(int i=0;i<8;i++){ if(array[i]==0){ array[i]=-1; box[step]=i; sort(step+1); array[i]=0; } } } public boolean isZhiShu(int sum){ if(sum==2||sum==3) return true; if(sum%6!=1&&sum%6!=5) return false; int temp=(int)Math.sqrt(sum); for(int i=5;i<=temp;i+=6){ if(sum%i==0||sum%(i+2)==0) return false; } return true; } public void start(){ sort(0); System.out.println(zhishu); } public static void main(String args[]){ Test2 test=new Test2(); test.start(); } }
转载请注明原文地址: https://www.6miu.com/read-1950064.html

最新回复(0)