## Editorial for New Year's '18 P2 - Mimi and Christmas Cake

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Let .

For of points, we can iterate through each slice of cake, and then all integers from to , to check if any of them are a factor of .

**Time Complexity:**

For an additional of points, we can process all the numbers from to , and record if they are prime or not in a boolean array, and then check if each is prime or not.

**Time Complexity:**

For the final of points, make the observation that if is a factor of and , then . Namely, we only have to check for factors in the range .

Alternatively, one could use a prime sieve, such as the sieve of Eratosthenes.

**Time Complexity:** or , or with the sieve of Eratosthenes.

## Comments