判断素数的四种方法

1.暴力破解

实现描述

1.若传入的数字小于2,则不符合素数的定义,抛出相应的异常
2.能够被除1与它本身以外的数整除的数,皆是非素数(即合数)
3.除2以外的偶数,皆有多个因数,所以除2以外的偶数皆是非素数(即合数)
4.数的最小因数必然不大于该数的平方根,通过计算平方根的结果进行循环可以避免不必要的计算流程

代码展示

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class PrimeNumberUtil {

	private static final Logger LOGGER = LoggerFactory.getLogger(PrimeNumberUtil.class);

    /**
     * 暴力求解<br>
     * 素数是大于1的自然数.除了1和它本身外,其他数都不是它的因子<br>
     * 2本身是素数,但除2以外的所有偶数都不是素数;也就是说除2以外,所有的质数都是奇数<br>
     * 非素数能够取余为0的最小因数不会超过它自身的平方根,若使用除法获取数的最小因数无法精确到位,从而造成不必要的循环
     * @param number 大于1的整数
     * @return 是否为素数
     */
    public static boolean violentSolution(int number) {

        /* 若数小于2,则输入错误 */
        if (number < 2) {
            LOGGER.error("inputs that do not meet the definition of prime numbers");
            return false;
        }

        if (number != 2 && number % 2 == 0) return false /* 数不等于2,且能被2取余为0,则该数不为质数 */;

        /* 取余数从3开始,每次循环完加2,保证取余数一直是奇数,循环的最大次数为数的平方根 */
        for (int i = 3; i <= Math.sqrt(number); i += 2) {
            /* 若数能被i取余为0,则该数不为质数 */
            if (number % i == 0) {
                return false;
            }
        }

        return true;

    }
}

2.素数表判断

实现描述

1.若传入的数字小于2,则不符合素数的定义,抛出相应的异常
2.若素数表中的最大数小于传入数字的平方根,则无法判断该数是否为素数,只能计算其支持的平方根范围内的数
3.若传入的数在素数表中存在的,则它一定是素数
4.若传入的数小于素数表中的最大数,且在素数表中不存在,则它不为素数
5.能够被素数表中的数整除,则不为素数
6.当素数表中循环到的数大于传入数字的平方根时,该数即为素数,可以结束当前循环

代码展示

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class PrimeNumberUtil {

	private static final Logger LOGGER = LoggerFactory.getLogger(PrimeNumberUtil.class);

	/** 0~100之间的所有质数 */
    public static final List<Integer> PRIME_NUMBERS;

    static {

        PRIME_NUMBERS = new ArrayList<>();

        PRIME_NUMBERS.add(2);
        PRIME_NUMBERS.add(3);
        PRIME_NUMBERS.add(5);
        PRIME_NUMBERS.add(7);
        PRIME_NUMBERS.add(11);
        PRIME_NUMBERS.add(13);
        PRIME_NUMBERS.add(17);
        PRIME_NUMBERS.add(19);
        PRIME_NUMBERS.add(23);
        PRIME_NUMBERS.add(29);
        PRIME_NUMBERS.add(31);
        PRIME_NUMBERS.add(37);
        PRIME_NUMBERS.add(41);
        PRIME_NUMBERS.add(43);
        PRIME_NUMBERS.add(47);
        PRIME_NUMBERS.add(53);
        PRIME_NUMBERS.add(59);
        PRIME_NUMBERS.add(61);
        PRIME_NUMBERS.add(67);
        PRIME_NUMBERS.add(71);
        PRIME_NUMBERS.add(73);
        PRIME_NUMBERS.add(79);
        PRIME_NUMBERS.add(83);
        PRIME_NUMBERS.add(89);
        PRIME_NUMBERS.add(97);

    }

    /**
     * 用素数表判断素数<br>
     * 素数是大于1的自然数.除了1和它本身外,其他数都不是它的因子<br>
     * 一个数如果不能整除比该数平方根小的任何素数,那么这个数就是素数<br>
     * 如果素数表中的最大值小于数的平方根,那么将无法保证判断出数是否是正确的素数
     * @param number 大于1的整数
     * @return 是否为素数
     */
    public static boolean primalityJudgmentPrimeNumber(int number) {

        /* 若数小于2,则输入错误 */
        if (number < 2) {
            LOGGER.error("inputs that do not meet the definition of prime numbers");
            return false;
        }

        int squareRoot = (int) Math.sqrt(number) /* 数的平方根 */;

        Integer maximumPrimeNumber = PRIME_NUMBERS.get(PRIME_NUMBERS.size() - 1);

        /* 若数的平方根大于素数表的最大数,则无法对该数进行素数判断 */
        if (maximumPrimeNumber < squareRoot) {
            LOGGER.error("beyond the scope of judgment");
            return false;
        }

        /* 若素数集合中不存在该数,则无法在此判断出该数是否为素数 */
        if (!PRIME_NUMBERS.contains(number)) {
            
            if (maximumPrimeNumber > number) return false /* 若素数表中的最大数大于传入的数字,则该数为非素数 */;
            
            /* 循环素数表 */
            for (Integer primeNumber : PRIME_NUMBERS) {
                if (primeNumber > squareRoot) break /* 当前从素数表中拿出的数大于数的平方根时,该数为质数,无需进行后续判断 */;
                if (number % primeNumber == 0) return false /* 数取余素数表中的数等于0时,该数不为素数 */;
            }
        }

        return true;

    }
}

3.埃拉托斯特尼(Eratosthenes)筛法

实现描述

有0 1 2 3 4 5 6 7 8 9 10,11个数想要获取其中的素数

1.先将不符合素数定义的数去除,得到: 2 3 4 5 6 7 8 9 10,也就是: false false true true true true true true true true true
2.用2将其倍数去除,得到: 2 3 5 7 9,也就是: false false true true false true false true false true false
3.用3将其倍数去除,得到: 2 3 5 7,也就是: false false true true false true false true false false false
4.由于素数除2以外,皆是奇数,跳过4直接判断5,得到: 2 3 5 7,也就是: false false true true false true false true false false false
5.跳过6直接判断7,得到: 2 3 5 7,也就是: false false true true false true false true false false false
6.跳过8直接判断9,得到: 2 3 5 7,也就是: false false true true false true false true false false false
7.跳过10直接判断11,因11大于10,循环结束

代码展示

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

    /**
     * 普通筛法 ------- 埃拉托斯特尼(Eratosthenes)筛法<br>
     * 将max范围内属于素数倍数的数剔除,剩余的即为素数<br>
     * 布尔数组默认值为false,把从索引2开始到数组末尾的元素全部改为true,表示后续的数需要进行判断才能够确定是否为素数
     * @param max 获取素数的最大范围,从0开始到max结束
     * @return 素数集合
     */
    public static List<Integer> ordinarySieve(int max) {

        long start = System.currentTimeMillis();

        List<Integer> list = new ArrayList<>() /* 素数集合 */;

        /* 若数小于2,则输入错误 */
        if (max < 2) {
            LOGGER.error("inputs that do not meet the definition of prime numbers");
            return list;
        }

        boolean[] judgmentSet = new boolean[max + 1] /* 布尔数组的默认值为false */;

        Arrays.fill(judgmentSet, 2, judgmentSet.length, true) /* 将数组中索引2到末尾的元素改为true */;

        int primary = 2;

        /* 当primary大于max时,结束循环 */
        while (primary <= max) {

            /* 将是primary倍数的对应索引的值改为false */
            for (int i = primary * primary; i < judgmentSet.length && i >= primary; i += primary) judgmentSet[i] = false;

            primary++;

            /* 在primary的值小于judgmentSet长度的情况下,若judgmentSet当前索引的值为false,就进行自增操作,表示该索引位置的值不需要进行判断 */
            while (primary < judgmentSet.length && !judgmentSet[primary]) primary++;

            /* 当primary大于等于judgmentSet的长度时,结束循环 */
            if (primary >= judgmentSet.length) break;

        }

        /* 循环judgmentSet数组 */
        for (int i = 0; i < judgmentSet.length; i++) {
            /* 若当前索引中的元素为true,则将当前索引添加到集合中 */
            if (judgmentSet[i]) {
                list.add(i);
            }
        }

        LOGGER.info("0~{}之间有{}个素数, 分别为: {},耗时: {}毫秒", max, list.size(), list, System.currentTimeMillis() - start);

        return list;

    }
}

4.欧拉筛法

实现描述

有0 1 2 3 4 5 6 7 8 9 10,11个数想要获取其中的素数

1.先将不符合素数定义的数去除,得到: 2 3 4 5 6 7 8 9 10
2.将2放入素数集合中,使用素数表中的数与其相乘,素数集合: 2,剩余: 3 5 6 7 8 9 10
3.将3放入素数集合中,使用素数表中的数与其相乘,素数集合: 2 3,剩余: 5 7 8 10
4.4已被删除,但要去除其平方以内的倍数,使用素数表中的数与其相乘,由于3乘以4大于10,循环会在此时结束,素数集合: 2 3,剩余: 5 7 10
5.将5放入素数集合中,使用素数表中的数与其相乘,由于3乘以5大于10,循环会在此时结束,素数集合: 2 3 5,剩余: 7
6.6已被删除,但要去除其平方以内的倍数,使用素数表中的数与其相乘,由于2乘以6大于10,循环会在此时结束,素数集合: 2 3 5,剩余: 7
7.将7放入素数集合中,使用素数表中的数与其相乘,由于2乘以7大于10,循环会在此时结束,素数集合: 2 3 5 7,至此循环就应该结束

代码展示

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PrimeNumberUtil {

    private static final Logger LOGGER = LoggerFactory.getLogger(PrimeNumberUtil.class);
 
    /**
     * 线性筛法 ------- 欧拉筛法<br>
     * 剔除被判断为非素数的数,避免重复判断<br>
     * 将判断为素数的数存储到集合中<br>
     * 将数与素数集合中的数相乘获取到非素数的数,将布尔数组中对应索引处的值改为false<br>
     * 为了避免重复判断,当素数集合中的数等于数本身时,结束循环,即数取余素数集合中的数等于0时(素数集合中的数都为素数,只有当数与集合中的某一个数相等时,才会主动结束循环,否则只能等循环自动结束)
     * @param max 获取素数的最大范围,从0开始到max结束
     * @return 素数集合
     */
    public static List<Integer> linearSieve(int max) {

        long start = System.currentTimeMillis();

        List<Integer> list = new ArrayList<>() /* 素数集合 */;

        /* 若数小于2,则输入错误 */
        if (max < 2) {
            LOGGER.error("inputs that do not meet the definition of prime numbers");
            return list;
        }

        boolean[] judgmentSet = new boolean[max + 1] /* 布尔数组的默认值为false */;

        Arrays.fill(judgmentSet, 2, judgmentSet.length, true) /* 将数组中索引2到末尾的元素改为true */;

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

            if (judgmentSet[i]) list.add(i) /* 若当前索引的值为true,则将其添加到集合中 */;

            /* 在索引值小于集合长度,且i索引值乘以集合中当前索引的值不大于max值的情况下循环素数集合 */
            for (int j = 0; j < list.size() && i * list.get(j) <= max; j++) {
                judgmentSet[i * list.get(j)] = false /* 将i与集合中当前索引值相乘索引处的元素改为false */;
                if (i == list.get(j)) break /* 集合中当前索引处值的平方等于i时,结束循环 */;
            }
        }

        LOGGER.info("0~{}之间有{}个素数, 分别为: {},耗时: {}毫秒", max, list.size(), list, System.currentTimeMillis() - start);

        return list;

    }
}