1.暴力破解 实现描述 1 2 3 4 1. 若传入的数字小于2 ,则不符合素数的定义,抛出相应的异常2. 能够被除1 与它本身以外的数整除的数,皆是非素数(即合数)3. 除2 以外的偶数,皆有多个因数,所以除2 以外的偶数皆是非素数(即合数)4. 数的最小因数必然不大于该数的平方根,通过计算平方根的结果进行循环可以避免不必要的计算流程
代码展示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import org.slf4j.Logger;import org.slf4j.LoggerFactory;public class PrimeNumberUtil { private static final Logger LOGGER = LoggerFactory.getLogger(PrimeNumberUtil.class); public static boolean violentSolution (int number) { 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 ; for (int i = 3 ; i <= Math.sqrt(number); i += 2 ) { if (number % i == 0 ) { return false ; } } return true ; } }
2.素数表判断 实现描述 1 2 3 4 5 6 1. 若传入的数字小于2 ,则不符合素数的定义,抛出相应的异常2. 若素数表中的最大数小于传入数字的平方根,则无法判断该数是否为素数,只能计算其支持的平方根范围内的数3. 若传入的数在素数表中存在的,则它一定是素数4. 若传入的数小于素数表中的最大数,且在素数表中不存在,则它不为素数5. 能够被素数表中的数整除,则不为素数6. 当素数表中循环到的数大于传入数字的平方根时,该数即为素数,可以结束当前循环
代码展示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 import org.slf4j.Logger;import org.slf4j.LoggerFactory;public class PrimeNumberUtil { private static final Logger LOGGER = LoggerFactory.getLogger(PrimeNumberUtil.class); 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 ); } public static boolean primalityJudgmentPrimeNumber (int number) { 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 ; } } return true ; } }
3.埃拉托斯特尼(Eratosthenes)筛法 实现描述
有0 1 2 3 4 5 6 7 8 9 10,11个数想要获取其中的素数
1 2 3 4 5 6 7 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 ,循环结束
代码展示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 import org.slf4j.Logger;import org.slf4j.LoggerFactory;import java.util.ArrayList;import java.util.Arrays;import java.util.List; public static List<Integer> ordinarySieve (int max) { long start = System.currentTimeMillis(); List<Integer> list = new ArrayList<>() ; if (max < 2 ) { LOGGER.error("inputs that do not meet the definition of prime numbers" ); return list; } boolean [] judgmentSet = new boolean [max + 1 ] ; Arrays.fill(judgmentSet, 2 , judgmentSet.length, true ) ; int primary = 2 ; while (primary <= max) { for (int i = primary * primary; i < judgmentSet.length && i >= primary; i += primary) judgmentSet[i] = false ; primary++; while (primary < judgmentSet.length && !judgmentSet[primary]) primary++; if (primary >= judgmentSet.length) break ; } for (int i = 0 ; i < judgmentSet.length; i++) { 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 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 ,至此循环就应该结束
代码展示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 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); public static List<Integer> linearSieve (int max) { long start = System.currentTimeMillis(); List<Integer> list = new ArrayList<>() ; if (max < 2 ) { LOGGER.error("inputs that do not meet the definition of prime numbers" ); return list; } boolean [] judgmentSet = new boolean [max + 1 ] ; Arrays.fill(judgmentSet, 2 , judgmentSet.length, true ) ; for (int i = 2 ; i <= max; i++) { if (judgmentSet[i]) list.add(i) ; for (int j = 0 ; j < list.size() && i * list.get(j) <= max; j++) { judgmentSet[i * list.get(j)] = false ; if (i == list.get(j)) break ; } } LOGGER.info("0~{}之间有{}个素数, 分别为: {},耗时: {}毫秒" , max, list.size(), list, System.currentTimeMillis() - start); return list; } }