diff options
author | Karl Shaffer <karlshaffer@google.com> | 2023-08-11 00:04:18 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2023-08-11 00:04:18 +0000 |
commit | d3fac44428dd0296a04a50c6827e3205b8dbea8a (patch) | |
tree | ace24ba4307d4978ee3134f7da671a77ad172da0 /src/main/java/org/apache/commons/math3/primes/Primes.java | |
parent | 5df6e262b13a4e2a008638ceea2b1f99db0d2331 (diff) | |
parent | 029d049e490dcd5fa609bb7632b0262d95f1bcce (diff) | |
download | apache-commons-math-android14-qpr2-s1-release.tar.gz |
Check-in commons-math 3.6.1 am: 1354beaf45 am: 0018f64b87 am: b3715644fb am: 5484895ffd am: 029d049e49HEADandroid-14.0.0_r37android-14.0.0_r36android-14.0.0_r35android-14.0.0_r34android-14.0.0_r33android-14.0.0_r32android-14.0.0_r31android-14.0.0_r30android-14.0.0_r29mastermainandroid14-qpr2-s5-releaseandroid14-qpr2-s4-releaseandroid14-qpr2-s3-releaseandroid14-qpr2-s2-releaseandroid14-qpr2-s1-releaseandroid14-qpr2-release
Original change: https://android-review.googlesource.com/c/platform/external/apache-commons-math/+/2702413
Change-Id: I6451550459c6d42417e3214f1db820289d799bc7
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
Diffstat (limited to 'src/main/java/org/apache/commons/math3/primes/Primes.java')
-rw-r--r-- | src/main/java/org/apache/commons/math3/primes/Primes.java | 124 |
1 files changed, 124 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/primes/Primes.java b/src/main/java/org/apache/commons/math3/primes/Primes.java new file mode 100644 index 0000000..4b003f9 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/primes/Primes.java @@ -0,0 +1,124 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.primes; + +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.util.List; + +/** + * Methods related to prime numbers in the range of <code>int</code>: + * + * <ul> + * <li>primality test + * <li>prime number generation + * <li>factorization + * </ul> + * + * @since 3.2 + */ +public class Primes { + + /** Hide utility class. */ + private Primes() {} + + /** + * Primality test: tells if the argument is a (provable) prime or not. + * + * <p>It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed: it + * uses the firsts prime numbers as successive base (see Handbook of applied cryptography by + * Menezes, table 4.1). + * + * @param n number to test. + * @return true if n is prime. (All numbers < 2 return false). + */ + public static boolean isPrime(int n) { + if (n < 2) { + return false; + } + + for (int p : SmallPrimes.PRIMES) { + if (0 == (n % p)) { + return n == p; + } + } + return SmallPrimes.millerRabinPrimeTest(n); + } + + /** + * Return the smallest prime greater than or equal to n. + * + * @param n a positive number. + * @return the smallest prime greater than or equal to n. + * @throws MathIllegalArgumentException if n < 0. + */ + public static int nextPrime(int n) { + if (n < 0) { + throw new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL, n, 0); + } + if (n == 2) { + return 2; + } + n |= 1; // make sure n is odd + if (n == 1) { + return 2; + } + + if (isPrime(n)) { + return n; + } + + // prepare entry in the +2, +4 loop: + // n should not be a multiple of 3 + final int rem = n % 3; + if (0 == rem) { // if n % 3 == 0 + n += 2; // n % 3 == 2 + } else if (1 == rem) { // if n % 3 == 1 + // if (isPrime(n)) return n; + n += 4; // n % 3 == 2 + } + while (true) { // this loop skips all multiple of 3 + if (isPrime(n)) { + return n; + } + n += 2; // n % 3 == 1 + if (isPrime(n)) { + return n; + } + n += 4; // n % 3 == 2 + } + } + + /** + * Prime factors decomposition + * + * @param n number to factorize: must be ≥ 2 + * @return list of prime factors of n + * @throws MathIllegalArgumentException if n < 2. + */ + public static List<Integer> primeFactors(int n) { + + if (n < 2) { + throw new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL, n, 2); + } + // slower than trial div unless we do an awful lot of computation + // (then it finally gets JIT-compiled efficiently + // List<Integer> out = PollardRho.primeFactors(n); + return SmallPrimes.trialDivision(n); + } +} |