Numbers With 3 Divisors
August 30, 2019
This is a trick question. Divisors come in pairs, so for most numbers the divisor-count is an even number; for instance, the divisors of 24 are 1 and 24, 2 and 12, 3 and 8, and 4 and 6, so 24 has 8 divisors. The only time a number can have an odd number of divisors is when the number is a perfect square; for instance, the divisors of 36 are 1 and 36, 2 and 18, 3 and 12, 4 and 9, and 6 and 6, the last two being duplicates, so 36 has 9 divisors. And the only time a number can have 3 divisors is when the number is a square of a prime; for instance, the divisors of 25 are 1, 5 and 25. I calculated the solution for n = 1,000,000,000 on my smart phone, using the PariDroid implementation of Pari/GP on Android:
primepi(sqrt(1e9)) = 3401
The answer comes back instantly. It’s amazing what a telephone can do these days; I used PariDroid to calculate the number of sexy primes between one billion and two billion in 62 seconds, less than double the time required on my desktop computer at home. If you need a Scheme solution, there’s one at https://ideone.com/R6tle6.
Programming Praxis 
Klong version
#?l@<l::l,{_1000000000%x}'l::1,2+&~{x!:\2+!_x^1%2}@1000000000 100 ?l@<l::l,{_1000000000%x}'l::1,2+&~{x!:\2+!_x^1%2}@1000000000 [1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000]@ProgrammingPraxis: Thanks again for the problem. Would be interesting to see the Pari/GP version of your solution. I didn’t make heads or tails of the Scheme one. Wish there was a Pari/GP version for iOS.
@bookofstevegraham: The Pari/GP version of my solution is given on the solution page: primepi(sqrt(1000000000000)).
The first line shows the number of divisors.
Tried this out on Python. Took me a while since I’m still basic. I learnt a lot from doing it. Only once I got the program to work did I realize that numbers with only 3 factors are just the squares of prime numbers, which led to me making the second, but more inefficient code.
l = list(range(1, int(input(“Choose a number :”))))
b = [] #Stores a number every time it’s modulo is 0
d = [] #The numbers with 3 factors
for i in l : #i is each term in l
a = list(range(1, int(1 + i))) #All values from 1 up to i
for c in a :
if i % c == 0 :
b.append(i)
if not len(b) == 3 :
b = [] #Clears the list for reuse
if len(b) == 3 :
d += b
b = [] #Clears the list for reuse
d = set(d) #Gets rid of duplicates
d = list(d)
print(d)
l = list(range(1, int(input(“Choose a number :”))))
print(“”)
b=[]
c=[]
for x in l :
y = x ** (1/2)
a = y
if y % 1 == 0 :
while a > 0 :
if y % a == 0 :
b.append(x)
a -= 1
if len(b) == 2 :
c.append(b)
else :
b = []
else :
continue
print(c)