can someone suggest optimizations to avoid TLE…
I am finding all primes using sieve then finding number of divisors of each number and then checking whether it is prime or not
1 Like
Don’t find number of divisors of all the numbers, use the fact that only perfect squares have odd number or factors
So find number of factors of perfect squares between the given range and check it to be prime, you can also store primes between [1,200] in another array because no number below 10^12 will have more than 200 factors.
This is will find numbers with prime number of factors which are not themselves prime, use sieve to count primes between the range
my code : http://www.codechef.com/viewsolution/2975477
Hope i made myself clear, if not I will be more than happy to elabortae
1 Like
what do you mean by “find number of factors of them” in second line? do you mean factors of factors of perfect squares?
sorry my bad, i edited it, i meant that according to question you are supposed to find number of factors of all the numbers in the given range, but do so only for perfect squares
well thanks…the only problem i am facing is in implementing sieve upto 10^12 can you help in some optimization?
You don’t need to sieve upto 10^12. You can perform segmented sieve for the given range [L,R] and count the number of factors for all numbers in that range. Then just check whether the counted number is prime or not (and for this you may use regular sieve upto 10^6). You can check my solution here: http://www.codechef.com/viewsolution/2935836
Yes, as kapildd said, though the range is 1 - 10^12 but its also mentioned that range <= 10^6 so that’s effectively sieve for 10^6 primes, check kapildd solution, if you want c++ see my above mentioned code, Cheers