Numbers With 3 Divisors
August 30, 2019
I saw this question on Stack Overflow a few days ago; it’s a well-known problem in number theory:
For a given number n, how many numbers less than n have exactly 3 divisors?
Your task is to write a program that counts the numbers less than n that have exactly 3 divisors, and use it to find the result when n is one billion. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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)