백준 21.12.08. 1929번 - 소수 구하기

import sys

M, N = map(int, sys.stdin.readline().split())

pn = []

for i in range(M, N+1):
    if i == 1:
        pass
    elif i == 2:
        pn.append(i)
    else:
        for j in range(2, i):
            if i % j == 0:                
                break
            elif j == i - 1:
                pn.append(i)

for _ in pn:
    print(_)

위와 같은 코드 또는 조금 더 정리된 코드로 작성해도 시간 초과가 나왔습니다. 

문제 알고리즘 분류에 있다.

그래서 검색을 해보니 "에라토스테네스의 체"를 사용해야 한다는데 무엇인지 찾아보았습니다.

---

 

위키백과

• 에라토스테네스의 체
  • 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.
• 알고리즘
  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
  2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  9. 자기 자신을 제외한 7의 배수를 모두 지운다.
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

• python(3.6.4)으로 구현

  • def prime_list(n):
        # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
        sieve = [True] * n
    
        # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
        m = int(n ** 0.5)
        for i in range(2, m + 1):
            if sieve[i] == True:           # i가 소수인 경우
                for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                    sieve[j] = False
    
        # 소수 목록 산출
        return [i for i in range(2, n) if sieve[i] == True]

---

• 식은 어느정도 이해가 되는데 n의 최대 약수가 sqrt(n) 즉, n의 제곱근 이하라는 점이 이해가 안 됩니다.
  • => 72의 최대 약수는 36 아닌가요?
    • => 아마 소인수분해에서의 약수를 뜻하는 것일 수도 있겠습니다.
    • 그러면 이해가 됩니다.

어쨌든 약수들의 배수들을 배제시키면서 소수를 찾아가는 과정이라는 것은 이해가 됐습니다.

def PrimeNumber(n):
    sieve = [True] * n
    print("sieve :", sieve)
    m = int(n ** 0.5)
    print("m :", m)
    for i in range(2, m + 1):
        print("i :", i)
        if sieve[i] == True:
            print("sieve[i] :", sieve[i])
            for j in range(i+i, n, i):
                print("j :", j)
                sieve[j] = False
            print("sieve :", sieve)
    print("sieve :", sieve)
    return [i for i in range(2, n) if sieve[i] == True]

print(PrimeNumber(12))

▲ 출력을 찍어서 어떻게 진행되는지 보았다.

 

이제 에라토스테네스의 체를 활용하여 소수를 구할 수 있으니 이것으로 문제를 풀면 됩니다.

 

def IsPrime(n):
    if n == 1:
        return False
    else:
        for i in range(2, int((n ** 0.5) + 1)):
            if n % i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N + 1):
    if IsPrime(i):
        print(i)

• 소수를 구하는 식을 살짝 변형했습니다.
• 굳이 리스트가 필요 없기 때문에 함수 정의 부분에서 bool값을 return 하는 형식으로 작성하여 True면 소수이기 때문에 출력하는 방식으로 작성했습니다.
• 우선 에라토스테네스의 체에서 약수는 구하려는 수의 제곱근 이하라고 했기 때문에 함수의 else문에서 반복문의 범위의 끝이 int((n ** 0.5) + 1)인 것입니다.
• 그리고 n이 i로 나눠진다면 False를 바로 반환하고 그렇지 않다면 반복문을 계속 돌리다가 True를 반환해줍니다.
• 그리고 이 함수를 본문에서 반복문으로 활용합니다.
• M이상 N이하의 범위에서 IsPrime함수에 매개변수로 i를 할당하여 i가 True라면 소수이기 때문에 출력해주고 False라면 출력하지 않고 다음 반복문을 실행합니다.