gistfile1.txt

x = p1 ^ a1 * p2 ^ a2 * ... * p_k ^ a_k
t = (a1 + 1) * (a2 + 1) * (a_k + 1) // number of divisors
a1 = 0 => a1 + 1 = 1

x = 9
x = 3 ^ 2
divisors = { 1, 3, 9 }
t = (2+1) is prime

x = 60
x = 2^2 * 3 * 5
divisors = { 1, 2, 4, 3, 6, 12, 5, 10, 20, 15, 30, 60 }
t = 
    (2 + 1) * // how many 2's to take
    (1 + 1) * // how many 3's to take
    (1 + 1)   // how many 5's to take
    = 12

t is prime <=> (a_k + 1) is prime & (a_i = 0 if i != k)
=>
x = p ^ a1: a1 > 1, p is prime, (a1 + 1) is prime


count i in l..r: i = p ^ q, p is prime, (q + 1) is prime


Sieve of Eratosphenes: get all primes in 2..10^7: