"Nikolay thinks an integer is interesting if it is a prime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number "
If it so, "Nikolay and Asya are happy when their tastes about some integer are common."
How come it can be true,  prime number is a number which does not have divisors except for 1 and itself, but it says ,in Asya sentence, that  "amount of its positive divisors is a prime number ",Does it mean 1 and the number given ?  Can somebody explain it to me and the sample given below the problem , please

Used Sieve to generate primes till 10^6, and then used those primes to generate larger primes.
counted all such numbers satisfying  L <= p^(q-1) <=R where p & q are primes (q>2). Subtracted it from R-L+1

How to optimize?

Remember that you shouldn't check prime numbers (They call an integer satisfying if they both consider or do not consider this integer to be interesting)

What is the test #85 ?

Edited by author 01.09.2016 22:25

Numbers liked by Asya only: https://oeis.org/A036454

1000 100000000000
99999971585

10 100
86

17 500
476