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.