문제 설명
문제풀이 KEY POINT
에라토스테네스의 체를 사용한 문제였다.
에라토스테네스의 체 알고리즘이란?
1. 2부터 N까지 모든 자연수 나열 후 전체 True처리
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 (i) 찾음
3. 남은 수 중에서 i의 배수를 모두 False 처리
4. 반복할 수 없을 때까지 2,3번 과정 반복
위 과정으로 진행되는 알고리즘으로, 배열 내 소수 찾기에 주로 사용된다.
import math
n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 지우기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
# 모든 소수 출력
for i in range(2, n + 1):
if array[i]:
print(i, end=' ')
풀이코드
이 문제에서 주의할 점은 시작 구간이 따로 정해져있다는 점이다.
처음에는 i의 배수 제거하는 부분에서 i를 시작 구간부터 설정했더니, 2의 배수, 3의 배수와 같이 작은 수의 배수가 소거되지 않는 문제가 있었다.
import math
a, b = map(int, input().split())
array = [i for i in range(a, b+1)]
array_T = [True for i in range(b+1)] #true이면 소수인것
for i in range(2, int(math.sqrt(b))+1):
if array_T[i] == True:
j = 2
while i*j <= b:
array_T[i*j] = False
j+=1
for i in range (a, b+1):
if array_T[i]:
print(str(array[i-a]), end=' ')