1929번: 소수 구하기

1. 코드

import math

x, y = map(int, input().split())
flag = []

for i in range(y+1):
    if i == 0 or i == 1: flag.append(False)
    else: flag.append(True)

for i in range(2, int(math.sqrt(y)+1)):
    if flag[i] == True:
        j = 2
        
        while i * j <= y:
            flag[i*j] = False
            j += 1
            
            
for i in range(x, y+1):
    if flag[i]: print(i)

2. 이해

문제 자체는 쉬운 내용이었습니다. 특정 범위 내의 소수를 찾아서 출력하면 되는데, 문제는 시간복잡도를 고려해야 한다는 점이었습니다. 그래서 에라토스테네스의 체를 배우고, 그 개념을 적용시켰습니다.

3. 구현

에라토스테네스의 체를 구현하는 과정은 크게 어렵지 않았습니다. 소수를 확인해야 하기 때문에 소수를 확인할 수 있는 리스트 자료형을 만들었고, 사전에 0과 1을 제외한 모든 값을 참으로 주었습니다. 그리고 반복문을 실행시켜서 소수를 판별해 주었고, 마지막으로 소수를 확인할 수 있는 리스트 자료형을 불러와 결괏값을 출력해 주었습니다.