UVa 294

From Algorithmist
Jump to navigation Jump to search

294 - Divisor[edit]


Given a range of numbers between 1 and 1,000,000,000 and the range of the numbers is no greater than 10,000 find the number in the range with the greatest number of divisors as well as the number of divisors it has.


The naive solution will not work here unfortunately which involves checking every single number with every single number. Just keep in mind that if you get a prime number that is very close to a billion you will be using sqrt(~1,000,000,000) operations to calculate the number of divisors each time.

  • However there is a formula for this problem that can be used to figure out how many factors there are. (here is an example)
1000=2^3 * 5^3
so 1000 has (3+1)*(3+1) factors.
1=1; because 1 is not prime.

A tip about speed improvement is to build a prime table.


1 10
1000 1000
999999900 1000000000


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.