Q7_10001st prime

들어가기

오늘 살펴볼 문제는 Q7 입니다.
https://projecteuler.net/problem=7

---

문항해설

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?

---

10001번째 소수가 무엇일지를 찾는 문제입니다.

---

예시코드

 우선 소수인지 판정하는 함수를 하나 만들어보도록 하겠습니다.
 자연수 $n$을 넣었을 때 소수이면 True를 , 소수가 아니면 False를 반환하는 함수를 작성해보도록 합시다.
아,!!
 어차피 만들어 놓은 것이 많을테니 한번 검색해보도록 하겠습니다.

https://www.geeksforgeeks.org/python-program-to-check-whether-a-number-is-prime-or-not/

 역시 있군요. 잘 읽어보면 수학적인 이론을 토대로 나름 효율적으로 판정하는 함수인 것 같습니다.

def isPrime(n):
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True

    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False

    i = 5
    while (i * i <= n):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
        i = i + 6

    return True

• 첫번째, 두번째 if에서 자연수가 1,2,3일 경우 각각 소수 판정을 해줍니다.
• 이제 4이상의 수에 대하여 세번째 if에서 2의 배수거나 3의 배수가 되면 False를 출력하고 함수를 끝냅니다.
• 이제는 2의 배수도 아니고, 3의 배수도 아닌 경우에 대하여 살펴봅니다.
• 이때에는 잘 생각해보면 $6k ± 1$꼴에 대해서만 판정을 하면 됩니다. 나머지 경우는 앞에서 이미 걸러졌습니다.
• while에서 체크하는 i는 $ 5,7 , 6+5, 6+7, 6 \times 2  +5 , 6 \times2  +7 \cdots $ 입니다. 즉, $6k ± 1$꼴에 대해서만 다시 검증해보고 있습니다.

---

이제 주어진 n에 대하여 n번째 소수를 출력하는 함수 nth_prime 를 구성해봅시다.

def nth_prime(n):
    mycount =0 
    mynumber =1
    while True:
        if isPrime(mynumber):
            mycount += 1

        if mycount == n :
            return mynumber

        mynumber +=1

print(nth_prime(10001)) # 104743

• mycount는 만들어지는 소수의 개수를 넣습니다.
• mynumber는 1부터 차례로 하나씩 증가시키면서 소수인지를 판단합니다.
• while안의 첫번째 if에서는 mynumber가 소수인지 판단하고 소수이면 개수를 1 증가시킵니다.
• while안의 두번째 if에서는 지금까지 만든 소수의 개수가 n이면 함수를 종료하고 그 소수를 반환합니다.
• if에 한번도 적용되지 않는 값(= 소수가 아닌 수)이 나오면 테스트하는 수를 1 증가합니다.
• while문안에 break가 없지만 종료됩니다. 함수안에 있는 return은 현재 걸려있는 모든 반복문을 종료하고 함수를 끝냅니다.

마무리

 드디어 소수가 사용되었네요. 소수는 앞으로도 많은 문제에서도 사용될 예정입니다. 오늘 만든 함수를 잘 저장해놓고 다시 재사용할 수 있어야 겠습니다. 재사용을 위해서는 import구문을 사용하면 되는데요. 다음에 나오는 예제에서 한번 다뤄보도록 하겠습니다.