介绍

质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数（素数）

解法

解法一：暴力枚举

枚举从2 ~ N的每一个数
实际上不用枚举到N，只需要枚举到√N就行

注意：

不要使用sqrt()函数，直接求√n，因为该函数运算较慢
注意数据溢出，i * i <= n可能会溢出，推荐使用i <= n / i

public static boolean isPrime(int n) {

       // 枚举到√n,注意溢出

       for(int i = 2; i <= n / i; i++)

           // 如果i可以整除n,说明n不是素数，直接return false

           if(n % i == 0)

               return false;

       // 说明n是素数

       return true;

}

解法二：埃氏筛法

public static boolean isPrime(int n){

    int [] arr = new int[n+1];

    // 1:质数   0:非质数

    Arrays.fill(arr,1);

    for(int i = 2; i <= n; i++){

        if(arr[i] == 1){

            // 将i的倍数去除掉

            for(int j = i+i; j <= n; j += i){

                arr[j] = 0;

            }

        }

    }

    return arr[n] == 1 ? true : false;

}

解法三：线性筛法

public static boolean isPrime3(int n){

    // 质数集合

    List<Integer> primes = new ArrayList<>();

    int [] arr = new int[n+1];

    // 1:质数   0:非质数

    Arrays.fill(arr,1);

    for(int i = 2; i <= n; i++){

        if(arr[i] == 1)

            primes.add(i); // 添加集合中

        // 筛选，

        for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){

            // 标记

            arr[i*primes.get(j)] = 0;

            // 保证每个合数只会被它的最小质因数筛去，减少冗余

            if(i % primes.get(j) == 0)

                break;

        }

    }

    return arr[n] == 1 ? true : false;

}

集合可以换成数组，用一个变量来保存当前集合中的质数数量，相当于下标

全部代码

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Prime{

    public static void main(String[] args) {

        System.out.println(isPrime(430348));

        System.out.println(isPrime2(430348));

        System.out.println(isPrime3(430348));

    }

    // 暴力枚举

    public static boolean isPrime(int n) {

        // 防止溢出

        for(int i = 2; i <= n / i; i++)

            if(n % i == 0)

                return false;

        return true;

    }

    // 埃氏筛法

    public static boolean isPrime2(int n){

        int [] arr = new int[n+1];

        // 1:质数   0:非质数

        Arrays.fill(arr,1);

        for(int i = 2; i <= n; i++){

            if(arr[i] == 1){

                // 将i的倍数去除掉

                for(int j = i+i; j <= n; j += i){

                    arr[j] = 0;

                }

            }

        }

        return arr[n] == 1 ? true : false;

    }

    // 线性筛法

    public static boolean isPrime3(int n){

        // 质数集合

        List<Integer> primes = new ArrayList<>();

        int [] arr = new int[n+1];

        // 1:质数   0:非质数

        Arrays.fill(arr,1);

        for(int i = 2; i <= n; i++){

            if(arr[i] == 1)

                primes.add(i); // 添加集合中

            // 筛选，

            for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){

                // 标记

                arr[i*primes.get(j)] = 0;

                // 保证每个合数只会被它的最小质因数筛去，减少冗余

                if(i % primes.get(j) == 0)

                    break;

            }

        }

        return arr[n] == 1 ? true : false;

    }

}

运行截图

巴特西

Java判断质数/素数的三种方法

介绍

解法

解法一：暴力枚举

解法二：埃氏筛法

解法三：线性筛法

全部代码

最新文章

热门文章