[프로젝트 오일러] Problem 3 Solution

프로젝트 오일러라는 사이트는 적당한 수학? 아이디어? 생각? 들을 배울 수 있는 사이트입니다.

http://euler.synap.co.kr/

Project Euler

사이트에 대한 자세한 내용은 위 링크로 들어가셔서 한번 보시면 될 것 같습니다.

 

문제 내용

3번 문제는 600851475143의 소인수 중에서 가장 큰 수을 구하는 문제입니다.

 

풀이

2부터 600851475143까지 숫자를 모두 탐색해가면서 600851475143의 약수이면서 소수인 수를 구하면 너무나 오래 걸릴 것입니다.(물론 코드를 제출하는 것이 아니라 답을 도출해내는 것이므로 그냥 계속 놔두면 언젠가는~~답이 나오겠죠. 하지만 답답합니다.) 그래서 다음 2가지의 생각을 해볼 수 있습니다.

 

1. 어떤 N이라는 수의 약수 중 소인수를 구할 때, 1부터 √N 까지의 숫자가 N의 약수인지 검사하면 된다.

2. 어떤 K라는 수가 소수인지 판단하는 과정은 2부터 √K 까지의 숫자로 K가 나누어떨어지는지 검사하면 된다. 

 

위의 아이디어를 코드로 바꾸면 이렇게 됩니다.

import math
N = 600851475143
ans = 1
for i in range(2,int(math.sqrt(N))+1):
    if N % i == 0:
        for j in range(2,int(math.sqrt(i))+1):
            if i %j == 0:
                break
        else:
            ans = i
print(ans)

 

답은 스스로 한번 코드를 작성하고 실행해보시길 바랍니다 :)

Rmx