You may also like

problem icon

Gaxinta

A number N is divisible by 10, 90, 98 and 882 but it is NOT divisible by 50 or 270 or 686 or 1764. It is also known that N is a factor of 9261000. What is N?

problem icon

Thirty Six Exactly

The number 12 = 2^2 3 has 6 factors. What is the smallest natural number with exactly 36 factors?

problem icon

Factoring Factorials

Find the highest power of 11 that will divide into 1000! exactly.

Flow Chart

Age 11 to 14 Challenge Level:

Vivek from UWCSEA showed a very clear understanding of what the flow chart does:

The numbers that lead to an output quickly have very small prime factors.
The numbers that don't, have very large prime factors.

The values of D that divide exactly into M are all prime numbers.

The value of N is the number of prime factors that the number has (e.g. 12 can be expressed as the product of 3 prime factors - 2 x 2 x 3 and the output when M = 12 is 3).

The flow chart helps you determine whether M is prime because if M is prime, the output is always 1: M can only be divided by D when D is the prime number itself. This makes it go around in a continuous loop without adding anything to N until M is divided by D (which equals to M), so N is always 1 when M is prime.