Problem
https://www.acmicpc.net/problem/1929
Solution
오답 코드1
1
2
3
4
5
6
7
8
9
10
def is_sosu(n):
for i in range(2,n):
if n % i == 0:
return 0
return 1
m, n = map(int, input().split())
for i in range(m, n+1):
if is_sosu(i) and i > 1:
print(i)
위 코드를 제출하니 바로 시간초과가 났다. 이 문제를 해결하기 위해 예전에 풀었던 문제에서 소수판별하는 범위를 n^0.5로 해서 해결했던 것을 떠올려 적용했다. 또한 입력, 출력을 받는 방법을 input(), print()대신 stdin.readline().split(), stdout.write()으로 바꿨다.
정답 코드1
1
2
3
4
5
6
7
8
9
10
11
12
from sys import stdin, stdout
def is_sosu(n):
for i in range(2,int(n**0.5)+1):
if n % i == 0:
return 0
return 1
m, n = map(int, stdin.readline().split())
for i in range(m, n+1):
if is_sosu(i) and i>1:
stdout.write(str(i)+'\n')
이렇게 제출한 뒤 정답처리가 됐지만 질문게시판을 확인해보니 에라토스테네스의 체라는 것을 활용해서도 시간초과 문제를 해결할 수 있다고 하였다.
정답 코드2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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())
final_list = [i for i in prime_list(n+1) if i>=m]
for i in final_list:
print(i)
Memo
‘에라토스테네스의 체’라는 개념을 통해 문제를 효율적으로 해결할 수 있다.