You are viewing a single comment's thread. Return to all comments →
For those who were wondering how to use sieve of eratosthenes here, this is the my modified sieve function
for powers of a prime number n (not including the prime itself), A[n] will be 0
for other numbers, A[n] will be one larger than the number of distinct prime factors
for example,
A[4]=0,
A[12]=3 (since 12 has 2 distinct prime factors 2 and 3),
A[1001]=4, so 1001 should have 3 distinct prime factors (indeed 7,11,13)
def sieve(n): A = [1]*(n+1) A[0], A[1] = 0, 0 for i in range(2,n+1): if A[i] == 1: for idx in range(1,n//i+1): A[i*idx]+=1 for po in range(2,int(math.log(n,i))+1): A[i**po] = 0 return A
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #47: Distinct primes factors
You are viewing a single comment's thread. Return to all comments →
For those who were wondering how to use sieve of eratosthenes here, this is the my modified sieve function
for powers of a prime number n (not including the prime itself), A[n] will be 0
for other numbers, A[n] will be one larger than the number of distinct prime factors
for example,
A[4]=0,
A[12]=3 (since 12 has 2 distinct prime factors 2 and 3),
A[1001]=4, so 1001 should have 3 distinct prime factors (indeed 7,11,13)