Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #The first two consecutive numbers to have two distinct prime factors are:
- #14 = 2 x 7
- #15 = 3 x 5
- #The first three consecutive numbers to have three distinct prime factors are:
- #644 = 2 x 2 x 7 x 23
- #645 = 3 x 5 x 43
- #646 = 2 x 17 x 19.
- #Find the first four consecutive integers to have four distinct prime factors.
- # What is the first of these numbers?
- def primes_sieve(limit):
- a = [True] * limit # Initialize the primality list
- a[0] = a[1] = False
- for (i, isprime) in enumerate(a):
- if isprime:
- yield i
- for n in xrange(i*i, limit, i): # Mark factors non-prime
- a[n] = False
- def primeFactors(n):
- """Return a list of the prime factors for a natural number."""
- if n == 1: return [1]
- primes = primes_sieve(int(n**0.5) + 1)
- factors = []
- for p in primes:
- if p*p > n:
- break
- while n % p == 0:
- factors.append(p)
- n //= p
- if n > 1:
- factors.append(n)
- return factors
- integers = []
- start = 210 #smallest number with 4 distinct prime factors 2*3*5*7
- while len(integers) != 4:
- #print start
- if len(set(primeFactors(start))) == 4 and\
- len(set(primeFactors(start+1))) == 4 and\
- len(set(primeFactors(start+2))) == 4 and\
- len(set(primeFactors(start+3))) == 4:
- integers = [start,start+1,start+2,start+3]
- start += 1
- print integers
Advertisement
Add Comment
Please, Sign In to add comment