Massive Algorithms: UVa 294: Divisors

UVa 294: Divisors | MathBlog

UVa 294: Divisors | MathBlog
https://uva.onlinejudge.org/external/2/294.html
Mathematicians love all sorts of odd properties of numbers. For instance, they consider 945 to be an interesting number, since it is the first odd number for which the sum of its divisors is larger than the number itself.

To help them search for interesting numbers, you are to write a program that scans a range of numbers and determines the number that has the largest number of divisors in the range. Unfortunately, the size of the numbers, and the size of the range is such that a too simple-minded approach may take too much time to run. So make sure that your algorithm is clever enough to cope with the largest possible range in just a few seconds.

Input Specification

The first line of input specifies the number N of ranges, and each of the N following lines contains a range, consisting of a lower bound L and an upper bound U, where L andU are included in the range. L and U are chosen such that

and

Output Specification

For each range, find the number P which has the largest number of divisors (if several numbers tie for first place, select the lowest), and the number of positive divisors D of P(where P is included as a divisor). Print the text 'Between L and H, P has a maximum of D divisors.', where L, H, P, and D are the numbers as defined above.

Example input

3
1 10
1000 1000
999999900 1000000000

Example output

Between 1 and 10, 6 has a maximum of 4 divisors.
Between 1000 and 1000, 1000 has a maximum of 16 divisors.
Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.

public static void main(String[] args) throws Exception {

    Scanner in = new Scanner(System.in);

    PrintWriter out = new PrintWriter(System.out, true);

    int tests = in.nextInt(); // read the number of tests

    // for each test

    for (int test = 0; test < tests; test++) {

        int L = in.nextInt(),    // read L

            U = in.nextInt(),    // read U

            maxDivisorCount = 0, // the maximum divisor count found

            maxNumber = 0;       // the number with the maximum divisor count

        // loop through the numbers

        for (int i = L; i <= U; i++) {

            // the divisor count of the current number

            // the divisorCount function calculates it for us

            int currentDivisorCount = divisorCount(i);

            // if the current divisor count is larger than

            // the largest divisor count (a contradiction),

            // then the current divisor count is the

            // largest divisor count

            if (currentDivisorCount > maxDivisorCount) {

                // update appropriate variables

                maxDivisorCount = currentDivisorCount;

                maxNumber = i;

}

}

        // output the result in the correct format

        out.printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, maxNumber, maxDivisorCount);

}

}

public static int divisorCount(int n) {

    // a counter for the number of divisors

    int count = 0;

    // loop through 1..n

    for (int i = 1; i <= n; i++)

        if (n % i == 0) // if the remainder of n divided by i is 0

            count++;    // then i is a divisor of n

    // return the number of divisors

    return count;

}

public static int divisorCount(int n) {

    // a counter for the number of divisors

    // intially 1 because n is a divisor of n

    int count = 1;

    // loop through 1..n/2

    for (int i = 1; i <= n / 2; i++)

        if (n % i == 0) // if the remainder of n divided by i is 0

            count++;    // then i is a divisor of n

    // return the number of divisors

    return count;

}

Now we’ll only loop from $1$ to $\sqrt{n}$ , and count each divisor we find, twice.

public static int divisorCount(int n) {

    if (n == 1)    // 1 is a tricky number,

        return 1;  // so we'll handle it separately

    // a counter for the number of divisors

    int count = 0;

    // save the square root to avoid re-computation

    int sqrt = (int)Math.sqrt(n);

    // loop through 1..sqrt(n)

    for (int i = 1; i <= sqrt; i++)

        if (n % i == 0) // if the remainder of n divided by i is 0

            count += 2; // then i and n/i are divisors of n

    // if n is a square number, then

    // we counted sqrt(n) twice

    if (sqrt * sqrt == n)

        count--; // so we fix the count

    // return the number of divisors

    return count;

}

Divisor Count through Prime Factorization
more generally for any number $n = p_0^{a_0} \times p_1^{a_1} \times \cdots \times p_n^{a_n}$ , where $p_i$ is the $i$ -th prime factor and $a_i$ is the power of that prime factor, it’s divisor count is $(a_0 1) \times (a_1 1) \times \cdots \times (a_n 1)$ .

public static int divisorCount(int n) {

    // a counter for the number of divisors

    // intially 1 (the multiplication identity)

    int count = 1;

    // save the square root to avoid re-computation

    int sqrt = (int)Math.sqrt(n);

    // loop through 2 and the odd numbers up to sqrt(n)

    for (int i = 2; i <= sqrt; i = (i == 2 ? 3 : i + 2)) {

        // a counter for the power of the

        // current number in the prime factorization

        int pow = 0;

        // while i is in n's prime factorization

        while (n % i == 0) {

            pow++;  // increment the power count

            n /= i; // remove one i from the prime factorization of n

}

        // if there were any i's in n's prime factorization

        if (pow != 0) {

            // change the divisor count according to our formula

            count *= pow + 1;

            // recompute the square root, since we've changed n

            // (a little optimization)

            sqrt = (int)Math.sqrt(n);

}

}

    // if we've still not removed all factors from n,

    // then there is one prime factor left

    if (n != 1)

        // change the divisor count according to our formula

        // (the power of the last prime is 1)

        count *= 1 + 1;

    // return the number of divisors

    return count;

}

https://en.wikipedia.org/wiki/Prime_factor

In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly.^[1] The prime factorization of a positive integer is a list of the integer's prime factors, together with theirmultiplicities; the process of determining these factors is called integer factorization. The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization.^[2]

To shorten prime factorizations, factors are often expressed in powers (multiplicities). For example,

360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5,

in which the factors 2, 3 and 5 have multiplicities of 3, 2 and 1, respectively.

Read full article from UVa 294: Divisors | MathBlog

UVa 294: Divisors | MathBlog

Input Specification

Output Specification

Example input

Example output

Labels

Popular Posts