超级素数
定义m位超级素数
(1)m位超级素数本身为素数。(2)从高位开始,去掉1位后为m-1位素数,去掉2位后为m-2位素数.....去掉m-1位后位1位素数。
枚举设计:
1.为方便判断素数,应用试商法设计素数判别函数p(k);
2.为枚举m位数需要,通过自乘10(即c=c*10),计算m位数的起始数c;
3.设置枚举m位奇数的f循环:
1)若f不是素数,或f的个位数字不是3或7(超级素数的个位数字必然是3或7),则返回;
2)若f的其他各位数字出现0,显然应排除;
3)除m位数f本身及其个位数已检验外,从高位开始去掉1位,2位,....,m-2位可得m-2个数,这m-2个数的p函数值相乘为t:
若t=0,说明m-2个数中至少有一个非素数,则返回。若t=1,说明m-2个数全为素数,应用变量作统计个数。
4)为输出最大的m位超级素数,在统计的同时,作赋值:e=法;最后输出的e则为最大的m位超级素数。
package test; import java.util.*; public class test1 { public static void main(String[] args) { int i,m; long c,d,e = 0,f,k,s,t; Scanner input=new Scanner(System.in); m=input.nextInt(); for(c=1,i=1;i<m;i++) c=c*10;//确定最小的m位数c s=0; for(f=c+1;f<10*c-1;f=f+2){ //设置枚举循环,f为m位奇数 if(p(f)==0||!(f%10==3||f%10==7)) continue; for(t=1,d=f/10,i=1;i<=m-2;i++){ if(d%10==0) t=0; //枚举中间m-2个数字 d=d/10; } if(t==0) continue; for(t=1,k=10,i=1;i<=m-2;i++){ k=k*10; t=t*p(f%k);//枚举m-2次去位操作 } if(t==0) continue; s++; e=f;//统计并赋值 } System.out.println("共"+s+"个"+m+"位超级素数"); System.out.println("其中最大数为"+e); } static int p(long k){//设计素数检测函数 int j,h,z; z=0; if(k==2)z=1; if(k>=3&&k%2==1){ for(h=0,j=3;j<=Math.sqrt(k);j+=2) if(k%j==0){ h=1; break; } if(h==0) z=1;//k为素数返回1,否则返回0 } return z; } }