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.math3.primes;
018
019import org.apache.commons.math3.exception.MathIllegalArgumentException;
020import org.apache.commons.math3.exception.util.LocalizedFormats;
021
022import java.util.List;
023
024
025/**
026 * Methods related to prime numbers in the range of <code>int</code>:
027 * <ul>
028 * <li>primality test</li>
029 * <li>prime number generation</li>
030 * <li>factorization</li>
031 * </ul>
032 *
033 * @since 3.2
034 */
035public class Primes {
036
037    /**
038     * Hide utility class.
039     */
040    private Primes() {
041    }
042
043    /**
044     * Primality test: tells if the argument is a (provable) prime or not.
045     * <p>
046     * It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed:
047     * it uses the firsts prime numbers as successive base (see Handbook of applied cryptography
048     * by Menezes, table 4.1).
049     *
050     * @param n number to test.
051     * @return true if n is prime. (All numbers &lt; 2 return false).
052     */
053    public static boolean isPrime(int n) {
054        if (n < 2) {
055            return false;
056        }
057
058        for (int p : SmallPrimes.PRIMES) {
059            if (0 == (n % p)) {
060                return n == p;
061            }
062        }
063        return SmallPrimes.millerRabinPrimeTest(n);
064    }
065
066    /**
067     * Return the smallest prime greater than or equal to n.
068     *
069     * @param n a positive number.
070     * @return the smallest prime greater than or equal to n.
071     * @throws MathIllegalArgumentException if n &lt; 0.
072     */
073    public static int nextPrime(int n) {
074        if (n < 0) {
075            throw new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL, n, 0);
076        }
077        if (n == 2) {
078            return 2;
079        }
080        n |= 1;//make sure n is odd
081        if (n == 1) {
082            return 2;
083        }
084
085        if (isPrime(n)) {
086            return n;
087        }
088
089        // prepare entry in the +2, +4 loop:
090        // n should not be a multiple of 3
091        final int rem = n % 3;
092        if (0 == rem) { // if n % 3 == 0
093            n += 2; // n % 3 == 2
094        } else if (1 == rem) { // if n % 3 == 1
095            // if (isPrime(n)) return n;
096            n += 4; // n % 3 == 2
097        }
098        while (true) { // this loop skips all multiple of 3
099            if (isPrime(n)) {
100                return n;
101            }
102            n += 2; // n % 3 == 1
103            if (isPrime(n)) {
104                return n;
105            }
106            n += 4; // n % 3 == 2
107        }
108    }
109
110    /**
111     * Prime factors decomposition
112     *
113     * @param n number to factorize: must be &ge; 2
114     * @return list of prime factors of n
115     * @throws MathIllegalArgumentException if n &lt; 2.
116     */
117    public static List<Integer> primeFactors(int n) {
118
119        if (n < 2) {
120            throw new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL, n, 2);
121        }
122        // slower than trial div unless we do an awful lot of computation
123        // (then it finally gets JIT-compiled efficiently
124        // List<Integer> out = PollardRho.primeFactors(n);
125        return SmallPrimes.trialDivision(n);
126
127    }
128
129}