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

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

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

Project Euler

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

 

문제 내용

7번 문제는 10001번째 소수를 구하는 문제입니다.

 

풀이

소수를 구하는 알고리즘은 너무나 많은 연구가 진행되고 여러 종류가 있지만

많이 사용하는 방법은 에라토스테네스의 채입니다.

 

에라토스테네스의 채에 관한 설명은 구글에 너무나 많은 글이 있으니 참고해주시기 바랍니다.

 

에라토스테네스의 채를 활용한 코드는 아래와 같습니다.

Mx = 150000
result = [0]

L = [i for i in range(Mx)]
L[0]=L[1] = -1


for i in range(2,Mx):
    if L[i] == i:
        result.append(i)
        for j in range(i+i,Mx,i):
            L[j] = -1

print(result[10001])

 

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

Rmx