Package de.tilman_neumann.jml
Class Divisors
java.lang.Object
de.tilman_neumann.jml.Divisors
public class Divisors
extends java.lang.Object
Implementations for finding all divisors of an integer.
-
Method Summary
Modifier and Type Method Description static java.math.BigInteger
getBiggestDivisorBelowSqrtN(java.math.BigInteger n)
Find the biggest divisor of n <= sqrt(n).static java.math.BigInteger
getBiggestDivisorBelowSqrtN(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)
Find the biggest divisor of n <= sqrt(n) given the prime factorization of n.static java.math.BigInteger
getDivisorCount(java.math.BigInteger n)
Computes the number of positive divisors of the given argument.static java.math.BigInteger
getDivisorCount(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)
Computes the number of positive divisors given the prime factorization of a number.static java.util.SortedSet<java.math.BigInteger>
getDivisors(java.math.BigInteger n)
Delivers the set of divisors of the argument, including 1 and n.static java.util.SortedSet<java.math.BigInteger>
getDivisors(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)
Bottom-up divisors construction algorithm.static java.util.SortedSet<java.math.BigInteger>
getDivisorsWithoutOneAndX(java.math.BigInteger n)
Delivers the set of divisors of the argument except for 1 and n.static java.util.SortedSet<java.math.BigInteger>
getSmallDivisors(java.math.BigInteger n)
static java.util.SortedSet<java.math.BigInteger>
getSmallDivisors(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)
Bottom-up divisors construction algorithm for all divisor <= sqrt(n).static java.util.ArrayList<java.math.BigInteger>
getSmallDivisors_v1(java.math.BigInteger n)
Compute all positive divisors d of n with d <= lower(sqrt(n)).static void
main(java.lang.String[] args)
Tests.static java.math.BigInteger
sumOfDivisors(java.math.BigInteger x)
static java.math.BigInteger
sumOfDivisors(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)
Fast sum of divisors when the prime factorization is known.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Method Details
-
getDivisors
public static java.util.SortedSet<java.math.BigInteger> getDivisors(java.math.BigInteger n)Delivers the set of divisors of the argument, including 1 and n.- Parameters:
n
- Argument.- Returns:
- The set of divisors of n, sorted smallest first.
-
getDivisors
public static java.util.SortedSet<java.math.BigInteger> getDivisors(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)Bottom-up divisors construction algorithm. Slightly faster than top-down.- Parameters:
factors
-- Returns:
- the set of divisors of the number thats prime factorization is given
-
getDivisorsWithoutOneAndX
public static java.util.SortedSet<java.math.BigInteger> getDivisorsWithoutOneAndX(java.math.BigInteger n)Delivers the set of divisors of the argument except for 1 and n.- Parameters:
n
- Argument.- Returns:
- The set of divisors of n.
-
getSmallDivisors_v1
public static java.util.ArrayList<java.math.BigInteger> getSmallDivisors_v1(java.math.BigInteger n)Compute all positive divisors d of n with d <= lower(sqrt(n)). Naive, slow implementation.- Parameters:
n
-- Returns:
- all divisors d of n with d <= lower(sqrt(n)).
-
getSmallDivisors
public static java.util.SortedSet<java.math.BigInteger> getSmallDivisors(java.math.BigInteger n) -
getSmallDivisors
public static java.util.SortedSet<java.math.BigInteger> getSmallDivisors(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)Bottom-up divisors construction algorithm for all divisor <= sqrt(n).- Parameters:
n
-factors
-- Returns:
- all divisor <= sqrt(n)
-
sumOfDivisors
public static java.math.BigInteger sumOfDivisors(java.math.BigInteger x)- Parameters:
x
-- Returns:
- The sum of all numbers 1<=d<=x that divide x. Faster implementation for general arguments. E.g. sumOfDivisors(6) = 1+2+3+6 = 12.
-
sumOfDivisors
public static java.math.BigInteger sumOfDivisors(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)Fast sum of divisors when the prime factorization is known. See https://www.math.upenn.edu/~deturck/m170/wk3/lecture/sumdiv.html.- Parameters:
factors
-- Returns:
- sum of divisors
-
getDivisorCount
public static java.math.BigInteger getDivisorCount(java.math.BigInteger n)Computes the number of positive divisors of the given argument.- Parameters:
n
-- Returns:
- number of divisors of n
-
getDivisorCount
public static java.math.BigInteger getDivisorCount(java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)Computes the number of positive divisors given the prime factorization of a number.- Parameters:
factors
-- Returns:
- number of divisors of n
-
getBiggestDivisorBelowSqrtN
public static java.math.BigInteger getBiggestDivisorBelowSqrtN(java.math.BigInteger n)Find the biggest divisor of n <= sqrt(n).- Parameters:
n
-- Returns:
- biggest divisor of n <= sqrt(n); 1 if n=1 or n prime
-
getBiggestDivisorBelowSqrtN
public static java.math.BigInteger getBiggestDivisorBelowSqrtN(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> factors)Find the biggest divisor of n <= sqrt(n) given the prime factorization of n.- Parameters:
n
-factors
- the factors of n as a map from primes to exponents- Returns:
- biggest divisor of n <= sqrt(n); 1 if n=1 or n prime
-
main
public static void main(java.lang.String[] args)Tests.- Parameters:
args
- Ignored.
-