PROBLEM LINK:Author DIFFICULTYEasy PREREQUISITESSieve of Eratosthenes , Sorting, Binary Search PROBLEMGiven an array of $N$ numbers, we have to find and print the overall ranking of supporters of the move. The rank must be in $ascending$ order. QUICK EXPLANATIONThe main body of the problem is finding if number of divisors of $P$ is an odd prime number or not. We first notice, that for number of divisors to be a prime number, the number $P$ must be of form $P$= ${a}^{b}$ , where $a$ is a prime number. Also, due to this, there are only some values of $P$ possible in range $[1,{10}^{12}]$ which can be supporters. Hence, we store all the possible values of ${P}$ (which are supporters) in an array/vector. Now, for every element in the (sorted) input array, we do a Binary search (in supporter's array) to check if its a supporter or not. If a value is found, it means ${P_i}$ is supporter. EXPLANATIONWhile reading the question, the very first thing coming to almost everyone's mind is same. That Again, as I always emphasize, tackling any question headon is not the best idea. Let us first give some in thinking. The question has specifically stated that for a person to be a supporter, ${P_i}$ must have an oddprime number of divisors. Its always fruitful to see the reason why setter takes pains to mention such small details! Let us first write $P$ in prime factorization form, and see if we can make an observation to solve this problem! Let We know by the high school formula, that number of divisors for ${P_i}$ will be $(a+1)*(b+1)*...(k+1)$ . Wait right there! Recall that our aim is see if number of divisors of ${P_i}$ is an odd $prime$ number or not. We ought to ask ourselves a question now, that, are number of divisors of ${P_i}$ prime? No! The number of divisors of ${P_i}$ is, in fact, divisible by $(a+1), (b+1) ,..., (k+1)$. Essentially, we notice one crucial fact, that, if ${P_i}$ is divisible by more than 1 prime number, then the number of its divisors will always be a product of 2 numbers (both greater than 1) and hence never prime. The above observation puts a very neat restriction, that ${P_i}$ must be expressible only in form of ${P_i}= {p_1}^{a}$ . More formally, we can say that ${P_i}$ must be a power of of prime. The number of divisors will then be (a+1), which can be prime. Also note, that ${P_i}$ cannot be a prime number either, since prime numbers have exactly 2 divisors, which is not an $odd$ prime number. This means, that a must be greater than 1. The minimum value of a is 2. Now we can use our initial approach of sieve! IMPLEMENTATION:First, we make a simple sieve to find and store all prime numbers upto ${10}^{6}$ . We choose our upper bound of ${10}^{6}$ as, after this, ${p_i}^{a}$ becomes greater than ${10}^{12}$, and hence out of concerned range. We make another array/vector to store all possible ${P_i}$ which are supporters. Now, for every prime number we stored, we keep on increasing its power (i.e. a) by 1 till ${p_i}^{a}$ gets out of range (i.e. greater than ${10}^{12}$ ). And, if we find that (a+1) is prime, we store ${p_i}^{a}$ in the newly created array. We can check if (a+1) is prime by using precomputations from our initial sieve. From now, the problem becomes really simple. We first sort the array so elements are in their respective positions/ranks and set our counter variable to 0 . We then start from the largest element (as ranks must be in ascending order). We check if ${P_i}$ is a supporter or not, by checking its presence in our previously created vector/array. We can do the search in O(logN) time by using Binary search. Alternatively, we can use inbuilt functions of the language (if any) so that we can avoid writing code for Binary search. For every supporter we come across, we increase our counter. If ${P_i}$ is a supporter, we can easily find its rank from its index in array. If counter variable is 0 after iterating through the entire array, it means that there are no supporters and we print Time Complexity: The code works in $O(Klog[log(K)] + NlogP)$ complexity, where $K$= ${10}^{6}$ (complexity of sieve) and $P$= size of array/vector with all supporters. SOLUTIONCOMMON SCOPE OF MISTAKESAre you still getting WA after reading this editorial? Make sure you haven't committed one of the common errors given below 1.Overflow in sieve Look at the pseudo code below.
Can you spot the error in it? Both i and j are int, and when i gets larger, j= i*i starts overflowing. Also, just declaring j as long long wont do. You must explicitly typecast the product to higher data type. The correct inner loop is given below
2.Printing RELATED PROBLEMSNoldback Problem  Quite Easy. CHEF VIJJU'S CORNER :D1.The Binary Search part can be coded very quickly if you know the inbuilt functions for your language. C++ users can use the function 2.What do you think about the Q if ${P_i}$ would be ${10}^{15}$? ${10}^{18}$ ? Will it be even solvable at this high limit? If yes, how, and if no, why? 3.I hope that this editorial somehow or the other, made you learn how to appreciate the small details provided by problem setters. I think most of us will agree on how the odd prime number made our life easy in this question! asked 02 Sep, 15:28

Nice Editorial. I didn't use Binary Search. First crucial observation is that. Pi must be expressible only in form of Pi=p1^a . Second observation is that . Since they want number of divisors(a+1) to be odd. It follows then that a should be even. It means that Pi needs to be perfect square. So, I sorted the Pi's . And, tried to factorize only if its perfect square. And while factorizing ,I broke (stop) from the factorization as soon as I found out that it has more than one distinct prime divisor. code Execution time : 0.10 s (although vijju123's one is lot faster :P ) answered 15 Nov, 13:07
1
Yes, great observation. I thought that I can use this question as an opportunity to introduce things like Your optimization is great as well :D
(15 Nov, 13:18)
1
Yep! The power of STL + I loved your approach too .
(15 Nov, 13:35)

Superb!! Great editorial!! You have raised the standard of editorials!! I have one question. I'm learning java from the past 6 months. I used binary search by referring this resource. Was not able to factorize to perfect square. Need your help. answered 06 Dec, 17:22

Finally these are getting posted <3