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