001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.numbers.primes;
018
019import java.util.List;
020
021/**
022 * Methods related to prime numbers in the range of <code>int</code>.
023 * <ul>
024 * <li>primality test</li>
025 * <li>prime number generation</li>
026 * <li>factorization</li>
027 * </ul>
028 */
029public final class Primes {
030    /** Exception message format when an argument is too small. */
031    static final String NUMBER_TOO_SMALL = "%d is smaller than the minimum (%d)";
032
033    /**
034     * Utility class.
035     */
036    private Primes() {}
037
038    /**
039     * Primality test: tells if the argument is a (provable) prime or not.
040     * <p>
041     * It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed:
042     * it uses the firsts prime numbers as successive base (see Handbook of applied cryptography
043     * by Menezes, table 4.1).
044     *
045     * @param n Number to test.
046     * @return true if {@code n} is prime. All numbers &lt; 2 return false.
047     */
048    public static boolean isPrime(int n) {
049        if (n < 2) {
050            return false;
051        }
052
053        for (final int p : SmallPrimes.PRIMES) {
054            if (0 == (n % p)) {
055                return n == p;
056            }
057        }
058        return SmallPrimes.millerRabinPrimeTest(n);
059    }
060
061    /**
062     * Return the smallest prime greater than or equal to n.
063     *
064     * @param n Positive number.
065     * @return the smallest prime greater than or equal to {@code n}.
066     * @throws IllegalArgumentException if n &lt; 0.
067     */
068    public static int nextPrime(int n) {
069        if (n < 0) {
070            throw new IllegalArgumentException(String.format(NUMBER_TOO_SMALL, n, 0));
071        }
072        if (n <= 2) {
073            return 2;
074        }
075        n |= 1; // make sure n is odd
076
077        if (isPrime(n)) {
078            return n;
079        }
080
081        // prepare entry in the +2, +4 loop:
082        // n should not be a multiple of 3
083        final int rem = n % 3;
084        if (0 == rem) { // if n % 3 == 0
085            n += 2; // n % 3 == 2
086        } else if (1 == rem) { // if n % 3 == 1
087            n += 4; // n % 3 == 2
088        }
089        while (true) { // this loop skips all multiple of 3
090            if (isPrime(n)) {
091                return n;
092            }
093            n += 2; // n % 3 == 1
094            if (isPrime(n)) {
095                return n;
096            }
097            n += 4; // n % 3 == 2
098        }
099    }
100
101    /**
102     * Prime factors decomposition.
103     *
104     * @param n Number to factorize: must be &ge; 2.
105     * @return the list of prime factors of {@code n}.
106     * @throws IllegalArgumentException if n &lt; 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}