[Project Euler] Q7. 10001st prime

Q7 : By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

 

구해야 할것

- prime number들을 구별해주는 부분

- prime number를 찾으면 count하여 10001번째까지 세주는 조건

 

코드

i = 0
n = 3
count = 1
check = 0

while True:
    for i in range(2, n):
        if n % i == 0:
            check = 1
            break
    if check == 0:
        count += 1

    if count == 10001:
        print(n)
        break
    n += 1
    check = 0

 

 

(1) 각 숫자마다 반복문을 통해 소수인지 아닌지를 체크 (이 부분에서 시간이 오래 걸린 것 같다.)

(2) 소수이면, check 값이 0이기 때문에 count += 1.

 

확인할 부분

- 에라토스테네스의 체 (소수를 찾는 방법 중 하나라 함)를 통해 구하는 방법을 알아봐야겠다.