Problem 47 - Find the first four consecutive integers to have four distinct primes factors.

링크

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

python

limit = 1000000 isPrime = [True] * limit isPrime[0] = isPrime[1] = False for i in range(2, int(round(limit**0.5))+1): if isPrime[i]: isPrime[2*i:limit:i] = [False] * ((limit-1)/i-1) primes = [x for x in range(2, limit) if isPrime[x]] def factors(n): cnt = 0 for p in primes: if p*p > n: cnt += 1 break if n % p == 0: cnt += 1 while n % p == 0: n /= p if n == 1: break return cnt q = 210 cnt = 0 print "start" while True and q < limit: if factors(q) == 4: cnt += 1 if cnt == 4: break else: cnt = 0 q += 1 print q