Project Euler. #3. Largest prime factor

By | 2013/02/11

Project Euler (http://projecteuler.net/) 문제3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195의 소인수는 5, 7, 13 그리고 29다.

600851475143의 소인수 중 가장 큰 수는?


p=600851475143

def isPrime(n):
    t=int(n**(1.0/2.0))
    while t>1:
        if n%t==0:
            return False
        else:
            t-=1
    return True

def isFactor(n):
    if p%n==0:
        return True
    else:
        return False

i = 2
while i<p:
    if isFactor(i):
        if isPrime(p/i):
            break
i+=1

print "The prime factor of %d is %d" % (p, (p/i))

이번 문제를 푸는데 한참을 헤맸다. 처음에 isPrime(n) 함수에서 n을 2부터 n-1까지 다 나눠보느라고 엄청난 시간을 소비하였다. 주어진 수가 무려 600,851,475,143 ... 6억이 넘는 수이므로 isPrime(n)에서 소수임을 판별하는데 어마어마한 시간을 소비할 수 밖에 없었다. 아마 24시간 기다려야 했을 것 같다. 한참을 생각하다가 굳이 다 나눠볼 필요없이 2에서 sqrt(n) 까지만 나눠보고 나누어 떨어지지 않으면 소수임을 알 수 있었다. 이렇게 하고 나니 1분 정도 기다리면 정답을 알아낼 수 있었다. 하지만 이렇게 1분 이상 기다려야 답을 보게 만든 문제가 아닐텐데... 뭔가 내가 코딩을 잘못한 것이 분명하다.


# by 'Michael J. Slee' on Project Euler

divisor = 2
number = 600851475143
while number != divisor:
while (number % divisor) == 0:
number = number / divisor
divisor = divisor + 1
print number

일단 문제를 해결하고 다른 사람들의 코드를 구경하다가 간단하면서도 명료한 코드를 찾았다. 파이썬 코드 중 긴 코드들은 제외하고 간단해 보이는 코드 몇개를 가져와서 실행해 봤는데 1초도 걸리지 않고 정답이 출력되었다. 역시, 내 코드에 큰 문제가 있다.

내 코드와 그리 큰 차이점이 있어보이지는 않는데, ... 아, 자세히 살펴보니 주어진 수가 소수임을 계산하는 과정에서 경우의 수를 기하급수적으로 줄이고 있다. 이 코드를 통해 힌트를 얻어서 기존의 내 코드를 수정해 보았다.


p=600851475143

def isPrime(n):
t=int(n**(1.0/2.0))
while t>1:
if n%t==0:
return False
else:
t-=1
return True

def isFactor(n):
if p%n==0:
return True
else:
return False

i = 2
while i