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.text.MessageFormat;
20 import java.util.List;
21
22 /**
23 * Methods related to prime numbers in the range of <code>int</code>.
24 * <ul>
25 * <li>primality test</li>
26 * <li>prime number generation</li>
27 * <li>factorization</li>
28 * </ul>
29 */
30 public final class Primes {
31 /** Exception message format when an argument is too small. */
32 static final String NUMBER_TOO_SMALL = "{0} is smaller than the minimum ({1})";
33
34 /**
35 * Utility class.
36 */
37 private Primes() {}
38
39 /**
40 * Primality test: tells if the argument is a (provable) prime or not.
41 * <p>
42 * It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed:
43 * it uses the firsts prime numbers as successive base (see Handbook of applied cryptography
44 * by Menezes, table 4.1).
45 *
46 * @param n Number to test.
47 * @return true if {@code n} is prime. All numbers < 2 return false.
48 */
49 public static boolean isPrime(int n) {
50 if (n < 2) {
51 return false;
52 }
53
54 for (final int p : SmallPrimes.PRIMES) {
55 if (0 == (n % p)) {
56 return n == p;
57 }
58 }
59 return SmallPrimes.millerRabinPrimeTest(n);
60 }
61
62 /**
63 * Return the smallest prime greater than or equal to n.
64 *
65 * @param n Positive number.
66 * @return the smallest prime greater than or equal to {@code n}.
67 * @throws IllegalArgumentException if n < 0.
68 */
69 public static int nextPrime(int n) {
70 if (n < 0) {
71 throw new IllegalArgumentException(MessageFormat.format(NUMBER_TOO_SMALL, n, 0));
72 }
73 if (n <= 2) {
74 return 2;
75 }
76 n |= 1; // make sure n is odd
77
78 if (isPrime(n)) {
79 return n;
80 }
81
82 // prepare entry in the +2, +4 loop:
83 // n should not be a multiple of 3
84 final int rem = n % 3;
85 if (0 == rem) { // if n % 3 == 0
86 n += 2; // n % 3 == 2
87 } else if (1 == rem) { // if n % 3 == 1
88 n += 4; // n % 3 == 2
89 }
90 while (true) { // this loop skips all multiple of 3
91 if (isPrime(n)) {
92 return n;
93 }
94 n += 2; // n % 3 == 1
95 if (isPrime(n)) {
96 return n;
97 }
98 n += 4; // n % 3 == 2
99 }
100 }
101
102 /**
103 * Prime factors decomposition.
104 *
105 * @param n Number to factorize: must be ≥ 2.
106 * @return the list of prime factors of {@code n}.
107 * @throws IllegalArgumentException if n < 2.
108 */
109 public static List<Integer> primeFactors(int n) {
110 if (n < 2) {
111 throw new IllegalArgumentException(MessageFormat.format(NUMBER_TOO_SMALL, n, 2));
112 }
113 return SmallPrimes.trialDivision(n);
114 }
115 }