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

Stage: 3 Challenge Level: Challenge Level:1

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.