Project Euler #47 - 네 개의 소인수를 갖는 연속된 네 수

프로젝트 오일러 47번 - distinct primes factors
연속되는 네 수이면서 각각의 소인수가 4개인 것 중 첫번째 숫자는?

sympy의 factorint를 이용하면 간단히 코딩할 수 있다.

from sympy import factorint

chk4 = 0
n = 10
while chk4 < 4:
    if len(factorint(n)) == 4: chk4 += 1
    else: chk4 = 0
    n += 1

print n -4

약 2초 동안 13만번의 소인수분해를 했다.
12번에서 썼던 소인수분해 함수를 다시 가져와 보면, 1.2초 정도로 시간이 줄어든다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def ndiv(n,pn):
    # n > 2
    i, fDic = 0, {}
    while True:
        p = pn[i]
        if n % p == 0:
            if p in fDic: fDic[p] += 1
            else: fDic[p] = 1
            n /= p
            i -= 1
        i += 1
        if pn[i]**2 > n and n > 1:
            if n in fDic: fDic[n] += 1
            else: fDic[n] = 1
            return fDic

pn = rwh_primes1(1000)

chk4 = 0
n = 10
while chk4 < 4:
    if len(ndiv(n,pn)) == 4: chk4 += 1
    else: chk4 = 0
    n += 1

print n -4