1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.numbers.primes;
18
19 import java.util.List;
20
21 /**
22 * Methods related to prime numbers in the range of <code>int</code>.
23 * <ul>
24 * <li>primality test</li>
25 * <li>prime number generation</li>
26 * <li>factorization</li>
27 * </ul>
28 */
29 public final class Primes {
30 /** Exception message format when an argument is too small. */
31 static final String NUMBER_TOO_SMALL = "%d is smaller than the minimum (%d)";
32
33 /**
34 * Utility class.
35 */
36 private Primes() {}
37
38 /**
39 * Primality test: tells if the argument is a (provable) prime or not.
40 * <p>
41 * It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed:
42 * it uses the firsts prime numbers as successive base (see Handbook of applied cryptography
43 * by Menezes, table 4.1).
44 *
45 * @param n Number to test.
46 * @return true if {@code n} is prime. All numbers < 2 return false.
47 */
48 public static boolean isPrime(int n) {
49 if (n < 2) {
50 return false;
51 }
52
53 for (final int p : SmallPrimes.PRIMES) {
54 if (0 == (n % p)) {
55 return n == p;
56 }
57 }
58 return SmallPrimes.millerRabinPrimeTest(n);
59 }
60
61 /**
62 * Return the smallest prime greater than or equal to n.
63 *
64 * @param n Positive number.
65 * @return the smallest prime greater than or equal to {@code n}.
66 * @throws IllegalArgumentException if n < 0.
67 */
68 public static int nextPrime(int n) {
69 if (n < 0) {
70 throw new IllegalArgumentException(String.format(NUMBER_TOO_SMALL, n, 0));
71 }
72 if (n <= 2) {
73 return 2;
74 }
75 n |= 1; // make sure n is odd
76
77 if (isPrime(n)) {
78 return n;
79 }
80
81 // prepare entry in the +2, +4 loop:
82 // n should not be a multiple of 3
83 final int rem = n % 3;
84 if (0 == rem) { // if n % 3 == 0
85 n += 2; // n % 3 == 2
86 } else if (1 == rem) { // if n % 3 == 1
87 n += 4; // n % 3 == 2
88 }
89 while (true) { // this loop skips all multiple of 3
90 if (isPrime(n)) {
91 return n;
92 }
93 n += 2; // n % 3 == 1
94 if (isPrime(n)) {
95 return n;
96 }
97 n += 4; // n % 3 == 2
98 }
99 }
100
101 /**
102 * Prime factors decomposition.
103 *
104 * @param n Number to factorize: must be ≥ 2.
105 * @return the list of prime factors of {@code n}.
106 * @throws IllegalArgumentException if n < 2.
107 */
108 public static List<Integer> primeFactors(int n) {
109 if (n < 2) {
110 throw new IllegalArgumentException(String.format(NUMBER_TOO_SMALL, n, 2));
111 }
112 return SmallPrimes.trialDivision(n);
113 }
114 }