# PROBLEM LINK:

**AJ and his Rosemilk audition**

PROBLEM CODE: AJRM

DIFFICULTY: Easy

The question asks us to classify numbers into 2 categories.

Rose number and Milk number. A Rose number is a number with exactly 3 distinct divisors.

We can check for the prime factorization for each number and tell if the number is a Rose number or a Milk number. But the range of the numbers given is 10^12. And it is not feasible to compute the prime factorization in the given time limit.

Another approach would be checking the properties of the numbers with exactly 3 divisors. We can see that every Rose number is a square of a PRIME number. So, if our numberâ€™s square root is a prime number, we can conclude that it is a Rose Number. Else, it is Milk number.

Time Complexity :

O(10^12) for calculating Sieve once. Then O(1) for each test case.

O(sqrt(n)) for calculating Prime in basic approach.

Setterâ€™s solution : Solution