Class Primes

java.lang.Object
org.episteme.core.mathematics.numbertheory.Primes
public class Primes extends Object
Prime number utilities including generation, testing, and factorization.

Implements classical number theory algorithms including the Sieve of Eratosthenes and the Miller-Rabin probabilistic primality test.

References

  • Eratosthenes of Cyrene, Sieve of Eratosthenes, circa 240 BCE (ancient algorithm)
  • Gary L. Miller, "Riemann's Hypothesis and Tests for Primality", Journal of Computer and System Sciences, Vol. 13, No. 3, 1976, pp. 300-317
  • Michael O. Rabin, "Probabilistic Algorithm for Testing Primality", Journal of Number Theory, Vol. 12, No. 1, 1980, pp. 128-138
Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

  • Constructor Details

    • Primes

      public Primes()

  • Method Details

    • isPrime

      public static boolean isPrime(BigInteger n)
      Tests if a number is prime.

      Uses trial division for small numbers and Miller-Rabin probabilistic test for large numbers (with high certainty).

      Parameters:
      n - the number to test
      Returns:
      true if probably prime

    • sieveOfEratosthenes

      public static List<Integer> sieveOfEratosthenes(int n)
      Generates primes up to n using Sieve of Eratosthenes.
      Parameters:
      n - upper limit
      Returns:
      list of primes up to n

    • factorize

      public static Map<BigInteger, Integer> factorize(BigInteger n)
      Computes prime factorization of n.
      Parameters:
      n - number to factorize
      Returns:
      map of prime factors to their exponents

    • nextPrime

      public static BigInteger nextPrime(BigInteger n)
      Returns the next prime after n.
      Parameters:
      n - starting number
      Returns:
      next prime number

    • gcd

      public static BigInteger gcd(BigInteger a, BigInteger b)
      Computes the greatest common divisor using Euclid's algorithm.
      Parameters:
      a - first number
      b - second number
      Returns:
      gcd(a, b)

    • lcm

      public static BigInteger lcm(BigInteger a, BigInteger b)
      Computes the least common multiple.
      Parameters:
      a - first number
      b - second number
      Returns:
      lcm(a, b)