[BOJ/Step9] 1929 : 소수 구하기 (Python)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

예제 입력 1

3 16

 

예제 출력 1

3

5

7

11

13

---

풀이 

(1) m과 n 사이 숫자를 각각 소수 판별

  1. 소수면 True를, 아니면 False를 반환하는 함수 is_prime(a)

    1-1. a가 1이면 return False

    1-2. a를 2~a-1의 수로 나눴을 때 나머지가 0이 되면 return False

    1-3. a를 2~a-1의 수로 모두 나눴는데 한번도 나머지가 0이 되지 않으면 return True

  2. m부터 n까지 a를 소수 판별, is_prime이 True를 반환할 때만 a 출력

# 1929-1.py

m, n = map(int, input().split())


def is_prime(a):
    if a == 1:
        return False
    for j in range(2, a):
        if a % j == 0:
            return False
    return True


for i in range(m, n+1):
    if is_prime(i):
        print(i)

 

(2) n까지의 수를 미리 소수 판별 후 확인
  1. prime 리스트안에 False, False, True, … 를 저장한다

      -> prime의 인덱스 숫자가 소수면 True, 그렇지 않으면 False를 저장할 것이다

  2. 에라토스테네스의 체를 이용한다.

    2-1. i는 2부터 n의 제곱근까지의 순서대로 배수를 지워나갈것.

            -> i의 배수는 i로 나눠지기 때문에 소수가 아니므로 prime[i]를 False로 변경

    2-2. prime[i] 가 True일 때만 배수를 지운다 -> False는 이미 더 이전에 지워진 것이므로 배수 또한 이미 False

    2-3. i*i부터 i씩 더하면서 False로 변경. i의 2배, 3배, …, n배는 더 이전에 이미 지워졌을것이므로 i*i부터 지워나간다

  3. 입력받은 m부터 n까지 prime[m] ~prime[n]의 값을 확인하여 True일 때만 출력한다

# 1929-2.py

m, n = map(int, input().split())
prime = [False, False] + [True] * (n - 1)
for i in range(2, int(pow(n, 0.5)+1)):
    if prime[i]:
        for j in range(i*i, n+1, i):
            prime[j] = False

for i in range(m, n+1):
    if prime[i]:
        print(i)

 

위가 (1)번 아래가 (2)번

(1)번은 속도는 느리지만 메모리 낭비가 적고

(2)번은 속도는 빠르지만 메모리 낭비가 크다

차이가 엄청남... 왜그런걸까