백준 1929번 풀이 - 파이썬(Python) (수학, 정수론, 에라토스테네스의 체)

문제 링크

https://www.acmicpc.net/problem/1929

문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

 

 

 

 

 

---

틀린 풀이

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

start_time = time.time()
# 2 ~ m의 리스트
array = list(range(2, m + 1))
array = [2] + [i for i in array if i % 2 == 1] # 2와 3 이상의 홀수만 남긴다

index = 0
while True:
		# 걸리지고 남은 맨 앞의 수부터 차례로 골라, 뒤에 있는 수를 나눠 소수를 판별한다 (에라토스테네스의 체)
    array = array[0:index + 1] + [i for i in array[index + 1:] if i % array[index] != 0]
    index += 1
		# 끝까지 다 진행한 경우 종료
    if index >= len(array):
        break
		# 사실 여기 올 일이 없음
    if array[index] >= m:
        break

# 위에서 2 ~ m 리스트로 시작했으니
# n 이상인지 판별하여 남긴다
result = [i for i in array if n <= i]
for number in result:
    print(number)

end_time = time.time()
print(end_time - start_time)

이유

• 시간초과
• 에라토스테네스의 체를 사용했으나, 시간복잡도가 너무 크다.

 

 

맞은 풀이1 (시간복잡도 상으로는 틀려야 한다..)

import time

start_time = time.time()
def check_prime(number):
    if number == 1:
        return False
    else:
        for i in range(2, int(number ** 0.5 + 1)):
            if number % i == 0:
                return False
        return True

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

for i in range(n, m + 1):
    if check_prime(i) == True:
        print(i)
end_time = time.time()

print(end_time - start_time)

접근 방식

• n이 소수인지 판별하려면, 1 ~ root(n) + 1 까지의 수로 나누어보면 된다.
• → 약수를 대칭을 이루므로, root(n) + 1 까지 나누어떨어지지 않는다면, 그 이상의 수로 나누어떨어질 일이 없기 때문.
• 해당 방식이 작은 수에는 더 많은 시간이 소요되지만, 큰 수에 대해서는 훨씬 적은 시간이 소요된다.
• 시간 복잡도 : O(N*N^0.5) → 10억 번의 연산으로 시간초과가 맞아 보인다..

 

 

 

맞은 풀이2

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

start_time = time.time()
array = list(range(2, m + 1))
array = [2] + [i for i in array if i % 2 == 1]

index = 0
while True:
    array = array[0:index + 1] + [i for i in array[index + 1:] if i % array[index] != 0]
    index += 1
    if index >= len(array):
        break
    if array[index] >= m ** 0.5 + 1:
        break

result = [i for i in array if n <= i]
for number in result:
    print(number)

end_time = time.time()
print(end_time - start_time)

접근 방식

• 에라토스테네스의 체를 이용한 풀이
• 에라토스테네스의 체를 사용할 때, 맞은 풀이1 처럼 m의 제곱근까지만 배수를 제거하였다. (그 이상의 배수는 존재하지 않는다! 이미 그 이하 수의 배수를 제거할 때 없어졌기 때문!)
• (연산이 간결해져서 훨씬 빠르다..)

 

 

맞은 풀이3

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]

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

N += 1
sieve = [True] * N
for i in range(2, int(N**0.5)+1):
    if sieve[i]:
        for j in range(2*i, N, i):
            sieve[j] = False
for i in range(M, N):
    if i > 1:
        if sieve[i]:
            print(i)

접근 방식

• 에라토스테네스의 체를 이용한 풀이
• 맞은 풀이2 를 보다 깔끔하게 정리한 풀이
• 실제 소수의 리스트를 남기는 것이 아니라, 1 ~ m(해당 코드에서는 n)까지의 True리스트를 만들고, 1 ~ squr(m) + 1의 배수에 해당하는 인덱스의 값을 False로 바꿨다.

 

 

 

정리

• 대량의 소수를 찾아야 한다!
  1. 에라토스테네스의 체 사용
  2. 1 ~ m 이 아닌, 1 ~ sqrt(m) + 1 까지만 배수를 제거하면 된다!