# Project Euler #47: Distinct primes factors

# Project Euler #47: Distinct primes factors

+ 2 comments Don't try to find every number's prime factors, you have no chance not to get timeout errors. Think about sieve of eratosthenes algorithm. Don't you go through all numbers with each prime. That's the trick.

+ 2 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

+ 1 comment Test your solution : 1000000 4 Truncated output 134043 238203 253894 259368 315720 319143 342054 351042 352884 354234 355508 357642 357643 380274 389388 ....... 993642 994344 996092

+ 7 comments I am a bit confused regarding the following test case: 37 2

There are 4 consequtive numbers which have 2 distinct prime factors:

`33: [3, 11] 34: [17, 2] 35: [5, 7] 36: [2, 3]`

Which is the expected answer for this range?

`33 35`

OR

`33`

+ 0 comments Wonderful challinging PE 47 problem version. Took my 3 hours to adapt sieve of eratosthenes but now I'm one step closer to stopping being a brute!

Sort 27 Discussions, By:

Please Login in order to post a comment