Package de.tilman_neumann.jml

Class Divisors

  • public class Divisors
extends Object
    Implementations for finding all divisors of an integer.
    Author:
    Tilman Neumann

    • Method Detail

      • getDivisors

        public static SortedSet<BigInteger> getDivisors​(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 SortedSet<BigInteger> getDivisors​(SortedMap<BigInteger,​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 SortedSet<BigInteger> getDivisorsWithoutOneAndX​(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 ArrayList<BigInteger> getSmallDivisors_v1​(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)).

      • sumOfDivisors

        public static BigInteger sumOfDivisors​(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 BigInteger sumOfDivisors​(SortedMap<BigInteger,​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 BigInteger getDivisorCount​(BigInteger n)
        Computes the number of positive divisors of the given argument.
        Parameters:
        n -
        Returns:
        number of divisors of n

      • getDivisorCount

        public static BigInteger getDivisorCount​(SortedMap<BigInteger,​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 BigInteger getBiggestDivisorBelowSqrtN​(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 BigInteger getBiggestDivisorBelowSqrtN​(BigInteger n,
                                                     SortedMap<BigInteger,​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​(String[] args)
        Tests.
        Parameters:
        args - Ignored.