求质数_java

求质数的方法：**

一、暴力法（计算超时）：

验证一个数是否为质数（素数）有很多方法。但最容易想到的莫非用暴力计算的方式一步步碾压过去的方法。虽然这种方法不是最优的，但是其对于我们了解素数仍是有所帮助的。

思路：验证某个数是否为质数时，将其对每一个比其小的数进行取余运算，并对取余为零的情况进行计数。由于质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。所以，当计数结果为 1 时，该数为质数。

在实际操作中，由于 1 和任意一个数必然取余为零，所以可以直接排除。并当没有取余为零的情况时，其才为质数。

得代码如下：

import java.util.Scanner;
public class zhishu {
   /* public static void main(String[]args){                              //暴力解法，最耗时耗力
        int i ;
        int j ;
        int count = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (i = 1;i<=n;i++){
            //boolean jg = true;
            for (j = 2;j<=i;j++){
                if(i%j==0){
                    //jg = false;
                    break;
                }
            }
            if(i==j){
                count +=1;
                System.out.print(i+"\t");
            }
        }
        System.out.println("");
        System.out.println(count);
    }*/

二、优化暴力算法：

细究暴力计算的方法，我们可以发现，假如一个数为 9 ，那么其二分之一（4.5）后的数都可以不用进行计算，因为肯定是有余的 。所以我们主要考虑i–i/2之间的数。

• 并且，我们可以发现，一切非 2 偶数一定不可能为质数。所以，我们可以在此处进行另一步的优化。

import java.util.Scanner;
public class zhishu {
/*public static void main(String[] args){                               //暴力解法的优化
    int count = 0;
    boolean sign;
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println("素数为：");
    for (int i = 2;i<=n;i++){            //1不是素数，从2开始循环
        if(i%2==0 && i!=2){              //排除偶数，不包含2（2是素数）
            continue;                    //到此结束，返回第一条命令开始循环
        }
         sign = true;
        for (int j = 2;j<=i/2;j++){      //只用求i的一半，i/2就能判断
            if(i%j==0){
                sign = false;
                break;
            }
        }
        if(sign){
            count +=1;
            System.out.print(i+"\t");
        }
    }
    System.out.println("");
    System.out.println("一共有："+count+"个");
}*/

public static void main(String[] args) {                               //暴力解法的优化
    int count = 0;
    boolean sign;
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println("素数为：");
    for (int i = 2; i <= n; i++) {           //1不是素数，从2开始循环
        if (i % 2 == 0 && i != 2) {          //排除偶数，不包含2（2是素数）
            continue;                   	 //到此结束，返回第一条命令开始循环
        }
        sign = true;
        for (int j = 2; j <= Math.sqrt(i); j++) {       //用开方过滤 Math.sqrt()
            if (i % j == 0) {
                sign = false;
                break;
            }
        }
        if (sign) {
            count += 1;
            System.out.print(i + "\t");
        }
    }
    System.out.println("");
    System.out.println("一共有：" + count + "个");

三、厄拉多塞筛法：

使用厄拉多塞筛法进行 1 到 64 的质数查找的过程如下：