princeofsudan

Project Euler #47 Distinct primes factors

Apr 8th, 2013
422
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.46 KB | None | 0 0
  1. #The first two consecutive numbers to have two distinct prime factors are:
  2.  
  3. #14 = 2 x 7
  4. #15 = 3 x 5
  5.  
  6. #The first three consecutive numbers to have three distinct prime factors are:
  7.  
  8. #644 = 2 x 2 x 7 x 23
  9. #645 = 3 x 5 x 43
  10. #646 = 2 x 17 x 19.
  11.  
  12. #Find the first four consecutive integers to have four distinct prime factors.
  13. # What is the first of these numbers?
  14.  
  15. def primes_sieve(limit):
  16.     a = [True] * limit                          # Initialize the primality list
  17.     a[0] = a[1] = False
  18.  
  19.     for (i, isprime) in enumerate(a):
  20.         if isprime:
  21.             yield i
  22.             for n in xrange(i*i, limit, i):     # Mark factors non-prime
  23.                 a[n] = False
  24.  
  25. def primeFactors(n):
  26.     """Return a list of the prime factors for a natural number."""
  27.     if n == 1: return [1]
  28.  
  29.     primes = primes_sieve(int(n**0.5) + 1)
  30.  
  31.     factors = []
  32.  
  33.     for p in primes:
  34.         if p*p > n:
  35.             break
  36.         while n % p == 0:
  37.             factors.append(p)
  38.             n //= p
  39.     if n > 1:
  40.         factors.append(n)
  41.  
  42.     return factors
  43.  
  44.  
  45. integers = []
  46. start = 210 #smallest number with 4 distinct prime factors 2*3*5*7
  47. while len(integers) != 4:
  48.     #print start
  49.     if len(set(primeFactors(start))) == 4 and\
  50.        len(set(primeFactors(start+1))) == 4 and\
  51.        len(set(primeFactors(start+2))) == 4 and\
  52.        len(set(primeFactors(start+3))) == 4:
  53.         integers = [start,start+1,start+2,start+3]
  54.     start += 1
  55. print integers
Advertisement
Add Comment
Please, Sign In to add comment