You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ra...@apache.org on 2017/09/16 17:35:05 UTC
[6/8] [math] MATH-1416: Remove Primes from commons-math as it have
been moved to commons-numbers
MATH-1416: Remove Primes from commons-math as it have been moved to commons-numbers
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/ae162d77
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/ae162d77
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/ae162d77
Branch: refs/heads/feature-MATH-1416
Commit: ae162d77621384c10ec037d3f7da7b00c16621c2
Parents: 9a3b7e4
Author: Ray DeCampo <ra...@decampo.org>
Authored: Sat Sep 16 13:17:40 2017 -0400
Committer: Ray DeCampo <ra...@decampo.org>
Committed: Sat Sep 16 13:17:40 2017 -0400
----------------------------------------------------------------------
.../org/apache/commons/math4/primes/Primes.java | 126 --------------
.../apache/commons/math4/primes/PrimesTest.java | 174 -------------------
2 files changed, 300 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/ae162d77/src/main/java/org/apache/commons/math4/primes/Primes.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/math4/primes/Primes.java b/src/main/java/org/apache/commons/math4/primes/Primes.java
deleted file mode 100644
index db75ccc..0000000
--- a/src/main/java/org/apache/commons/math4/primes/Primes.java
+++ /dev/null
@@ -1,126 +0,0 @@
-/*
- * 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.math4.primes;
-
-import org.apache.commons.math4.exception.MathIllegalArgumentException;
-import org.apache.commons.math4.exception.util.LocalizedFormats;
-
-import java.util.List;
-
-
-/**
- * Methods related to prime numbers in the range of <code>int</code>:
- * <ul>
- * <li>primality test</li>
- * <li>prime number generation</li>
- * <li>factorization</li>
- * </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);
- }
- return SmallPrimes.trialDivision(n);
-
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/ae162d77/src/test/java/org/apache/commons/math4/primes/PrimesTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math4/primes/PrimesTest.java b/src/test/java/org/apache/commons/math4/primes/PrimesTest.java
deleted file mode 100644
index 831a86e..0000000
--- a/src/test/java/org/apache/commons/math4/primes/PrimesTest.java
+++ /dev/null
@@ -1,174 +0,0 @@
-/*
- * 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.math4.primes;
-
-
-import java.util.HashSet;
-import java.util.List;
-
-import org.apache.commons.math4.exception.MathIllegalArgumentException;
-import org.apache.commons.math4.exception.util.LocalizedFormats;
-import org.apache.commons.math4.primes.Primes;
-import org.apache.commons.math4.primes.SmallPrimes;
-import org.junit.Assert;
-import org.junit.Test;
-
-public class PrimesTest {
-
- public static final int[] PRIMES = {//primes here have been verified one by one using Dario Alejandro Alpern's tool, see http://www.alpertron.com.ar/ECM.HTM
- 2,3,5,7,11,13,17,19,23,29,31,43,47,53,71,73,79,89,97,
- 107,137,151,157,271,293,331,409,607,617,683,829,
- 1049,1103,1229,1657,
- 2039,2053,//around first boundary in miller-rabin
- 2251,2389,2473,2699,3271,3389,3449,5653,6449,6869,9067,9091,
- 11251,12433,12959,22961,41047,46337,65413,80803,91577,92693,
- 118423,656519,795659,
- 1373639,1373677,//around second boundary in miller-rabin
- 588977,952381,
- 1013041,1205999,2814001,
- 22605091,
- 25325981,25326023,//around third boundary in miller-rabin
- 100000007,715827881,
- 2147483647//Integer.MAX_VALUE
- };
-
- public static final int[] NOT_PRIMES = {//composite chosen at random + particular values used in algorithms such as boundaries for millerRabin
- 4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,
- 275,
- 2037,2041,2045,2046,2047,2048,2049,2051,2055,//around first boundary in miller-rabin
- 9095,
- 463465,
- 1373637,1373641,1373651,1373652,1373653,1373654,1373655,1373673,1373675,1373679,//around second boundary in miller-rabin
- 25325979,25325983,25325993,25325997,25325999,25326001,25326003,25326007,25326009,25326011,25326021,25326025,//around third boundary in miller-rabin
- 100000005,
- 1073741341,1073741823,2147473649,2147483641,2147483643,2147483645,2147483646};
-
- public static final int[] BELOW_2 = {
- Integer.MIN_VALUE,-1,0,1};
-
- void assertPrimeFactorsException(int n, Throwable expected) {
- try {
- Primes.primeFactors(n);
- Assert.fail("Exception not thrown");
- } catch (Throwable e) {
- Assert.assertEquals(expected.getClass(), e.getClass());
- if (expected.getMessage() != null) {
- Assert.assertEquals(expected.getMessage(), e.getMessage());
- }
- }
- }
- void assertNextPrimeException(int n, Throwable expected){
- try {
- Primes.nextPrime(n);
- Assert.fail("Exception not thrown");
- } catch(Throwable e) {
- Assert.assertEquals(expected.getClass(), e.getClass());
- if (expected.getMessage() != null) {
- Assert.assertEquals(expected.getMessage(), e.getMessage());
- }
- }
- }
-
- @Test
- public void testNextPrime() {
-
- Assert.assertEquals(2, Primes.nextPrime(0));
- Assert.assertEquals(2, Primes.nextPrime(1));
- Assert.assertEquals(2, Primes.nextPrime(2));
- Assert.assertEquals(3, Primes.nextPrime(3));
- Assert.assertEquals(5, Primes.nextPrime(4));
- Assert.assertEquals(5, Primes.nextPrime(5));
-
- for (int i = 0; i < SmallPrimes.PRIMES.length - 1; i++) {
- for (int j = SmallPrimes.PRIMES[i] + 1; j <= SmallPrimes.PRIMES[i + 1]; j++) {
- Assert.assertEquals(SmallPrimes.PRIMES[i+1], Primes.nextPrime(j));
- }
- }
-
- Assert.assertEquals(25325981, Primes.nextPrime(25325981));
- for (int i = 25325981 + 1; i <= 25326023; i++) {
- Assert.assertEquals(25326023, Primes.nextPrime(i));
- }
-
- Assert.assertEquals(Integer.MAX_VALUE, Primes.nextPrime(Integer.MAX_VALUE - 10));
- Assert.assertEquals(Integer.MAX_VALUE, Primes.nextPrime(Integer.MAX_VALUE - 1));
- Assert.assertEquals(Integer.MAX_VALUE, Primes.nextPrime(Integer.MAX_VALUE));
-
- assertNextPrimeException(Integer.MIN_VALUE, new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL,Integer.MIN_VALUE,0));
- assertNextPrimeException(-1, new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL,-1,0));
- assertNextPrimeException(-13, new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL,-13,0));
- }
-
- @Test
- public void testIsPrime() throws Exception {
- for (int i : BELOW_2) {
- Assert.assertFalse(Primes.isPrime(i));
- }
- for (int i:NOT_PRIMES) {
- Assert.assertFalse(Primes.isPrime(i));
- }
- for (int i:PRIMES) {
- Assert.assertTrue(Primes.isPrime(i));
- }
- }
-
- static int sum(List<Integer> numbers){
- int out = 0;
- for (int i:numbers) {
- out += i;
- }
- return out;
- }
- static int product(List<Integer> numbers) {
- int out = 1;
- for (int i : numbers) {
- out *= i;
- }
- return out;
- }
- static final HashSet<Integer> PRIMES_SET = new HashSet<>();
- static {
- for (int p : PRIMES) {
- PRIMES_SET.add(p);
- }
- }
- static void checkPrimeFactors(List<Integer> factors){
- for (int p : factors) {
- if (!PRIMES_SET.contains(p)) {
- Assert.fail("Not found in primes list: " + p);
- }
- }
- }
-
- @Test
- public void testPrimeFactors() throws Exception {
- for (int i : BELOW_2) {
- assertPrimeFactorsException(i, new MathIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL,i,2));
- }
- for (int i : NOT_PRIMES) {
- List<Integer> factors = Primes.primeFactors(i);
- checkPrimeFactors(factors);
- int prod = product(factors);
- Assert.assertEquals(i, prod);
- }
- for (int i : PRIMES) {
- List<Integer> factors = Primes.primeFactors(i);
- Assert.assertEquals(i, (int)factors.get(0));
- Assert.assertEquals(1, factors.size());
- }
- }
-}