你的位置:首页 > Java教程

[Java教程]Java学习第一天:数据基础,打印质数的实现



第一天正式学习Java,写下这篇关于质数求解的文章,希望能更改进的更好。

首先说,以前在C上求解过质数的问题,当时没怎么在意。一直用的方法是从2开始递增到n-1,如果在这个过程中有一个数能被n整除,那么这个数就不是质数。这样做当然是没问题的最简单的一种方法。

之后看了一些文章的介绍,随着数学知识的增长,今天在学习Java语言上实现了这个想法,把这一过程记录如下:


先从最原始的递增法说起:

1、除了2之外,全部的质数是奇数,所以,循环数可以减少一般。

2、递增的界限不应是n-1,可以加以优化。对于整数N,存在最大的n,使得n的平方<=N,在自然数范围内,N必定可以分解为两个数的乘积,假设分解的结果是n1*n2=N,且n1<n2;那么必定有n1<n<n2。这样得出结论,在求质数的过程中,递增的最大的界限是N的二次方根。

3、实现代码:(java)

// 判断一个是是否是质数
Scanner input=new Scanner(System.in);
System.out.println("请输入数字:");
int number=input.nextInt();
boolean flag=true;

//if..else:当输入的数小于2时,显示错误;当输入的是2时,显示是质数,当输入的是大于2的数时,开始循环判断
if(number<2){
    System.out.println("输入非法,请输入大于2的整数。程序终止");
}else if(number==2){
    System.out.println("2 是质数");
}else{
   
    //如果能被2整除修改flag,否则从3开始for循环判断是否修改flag
    if(number%2==0){
        flag=false;
    }else{
            for(int i=3;i<=Math.sqrt(number);i+=2){
                if(number%i==0){
                    flag=false;
                    break;
                }
            }
        }
   
    //根据flag是否被修改,判断时候是质数
    if(flag){
        System.out.println(number+"是质数");
    }else{
        System.out.println(number+"不是质数");
    }
}

4、对于打印n内所有的质数的问题,用上面的方法一个一个的判断是非常浪费资源的。使用晒法打印效率会高很多。

5、晒法的基本思想是除去N内所有质数倍数的数,剩下的就是质数,比如打印10以内的质数:

从a=2开始,先除去2倍数的数,即4、6、8;

a++,3,没被除去必是质数,再除去3倍数的数,6,9;

a++,4,已经被除去,循环继续;

a++,5,没被除去必是质数,除去5的倍数10;

到这步,由于至少需要除去质数的2倍的数,即,循环的最大数是n/2。对于大于n/2再处理,如果它没有被前面的操作除去,那么它必定是质数。

代码实现(Java):

//筛选法,实现100以内所有素数的打印
        byte[] bl=new byte[100];
       
        //k用来存储每个待除去的数组下标
        int k;
        //将所有的值设为1
        for(int j=0;j<100;j++){
            bl[j]=1;
        }
       
        //晒法实现去除所有非质数
        for(int i=1;i<=50;i+=1){
            //如果这个数组值不为1,则继续
            if(bl[i]==0){
                continue;
            }
            for(int j=i;j<100/(i+1);j++){
                k=(i+1)*(j+1)-1;
                bl[k]=0;
            }
        }
        System.out.print('2'+" ");
        for(int i=2;i<100;i+=2){
            if(bl[i]==1)
                System.out.print((i+1)+" ");
        }
        System.out.println();     //结果应该是    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
     }