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.text.MessageFormat;
020import java.util.List;
021
022/**
023 * Methods related to prime numbers in the range of <code>int</code>.
024 * <ul>
025 * <li>primality test</li>
026 * <li>prime number generation</li>
027 * <li>factorization</li>
028 * </ul>
029 */
030public final class Primes {
031    /** Exception message format when an argument is too small. */
032    static final String NUMBER_TOO_SMALL = "{0} is smaller than the minimum ({1})";
033
034    /**
035     * Utility class.
036     */
037    private Primes() {}
038
039    /**
040     * Primality test: tells if the argument is a (provable) prime or not.
041     * <p>
042     * It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed:
043     * it uses the firsts prime numbers as successive base (see Handbook of applied cryptography
044     * by Menezes, table 4.1).
045     *
046     * @param n Number to test.
047     * @return true if {@code n} is prime. All numbers &lt; 2 return false.
048     */
049    public static boolean isPrime(int n) {
050        if (n < 2) {
051            return false;
052        }
053
054        for (final int p : SmallPrimes.PRIMES) {
055            if (0 == (n % p)) {
056                return n == p;
057            }
058        }
059        return SmallPrimes.millerRabinPrimeTest(n);
060    }
061
062    /**
063     * Return the smallest prime greater than or equal to n.
064     *
065     * @param n Positive number.
066     * @return the smallest prime greater than or equal to {@code n}.
067     * @throws IllegalArgumentException if n &lt; 0.
068     */
069    public static int nextPrime(int n) {
070        if (n < 0) {
071            throw new IllegalArgumentException(MessageFormat.format(NUMBER_TOO_SMALL, n, 0));
072        }
073        if (n <= 2) {
074            return 2;
075        }
076        n |= 1; // make sure n is odd
077
078        if (isPrime(n)) {
079            return n;
080        }
081
082        // prepare entry in the +2, +4 loop:
083        // n should not be a multiple of 3
084        final int rem = n % 3;
085        if (0 == rem) { // if n % 3 == 0
086            n += 2; // n % 3 == 2
087        } else if (1 == rem) { // if n % 3 == 1
088            n += 4; // n % 3 == 2
089        }
090        while (true) { // this loop skips all multiple of 3
091            if (isPrime(n)) {
092                return n;
093            }
094            n += 2; // n % 3 == 1
095            if (isPrime(n)) {
096                return n;
097            }
098            n += 4; // n % 3 == 2
099        }
100    }
101
102    /**
103     * Prime factors decomposition.
104     *
105     * @param n Number to factorize: must be &ge; 2.
106     * @return the list of prime factors of {@code n}.
107     * @throws IllegalArgumentException if n &lt; 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}