枚举-超级素数搜索

超级素数
定义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;
    }
    
}
原文地址:https://www.cnblogs.com/ljs-666/p/8119933.html