Which positive 3-digit integer has the most positive integer divisors?
Source: Based on "2001 Mensa Puzzle Calendar" puzzle for October 13
Here's a problem that's simple to solve with a program but not easy with pencil & paper. There may be a trick to solve it simply by hand, but I haven't found it.
For this program, we'll just try all integers, n, from 100 to 999 in a loop and for each n check all divisors from 1 to n / 2. To satisfy the requirements of the problem, all we have to do is check the number of divisors found for each n against maxdivisors, the maximum found so far. and save n and maxdivisors whenever a higher value is found.
Delphi's remainder function. mod, is the easy way to check for divisors, if "number mod trialdivisor = 0" then trialdivisor is a divisor.
We'll add a few more lines of code here to display the divisors, just in case someone wants to check our answer.
|
What is the maximum number of divisors for 4 digit numbers? |
|
5 digit numbers? (Be warned - using this technique for the 5 digits case will execute about a billion trial divisions, so be prepared to wait for a few of minutes.) |
|
How could the algorithm be made faster? Hint: each successful division should give us 2 divisors and let us lower the upper limit of potential divisors that we need to check. |