[백준] 1929번 소수 구하기

💡문제접근

• 에라토스테네스의 체를 이용해 N까지의 배열을 만든 다음 소수면 True, 합성수거나 0, 1이면 False를 넣고 조건문을 돌려 True이면서 M이상 N이하의 범위를 만족한다면 값을 출력하도록 코드를 작성했다.
• 그런데 N까지의 배열을 만들면 M미만의 값이 포함되어 공간이 낭비될 수 있어 좋지 못한 코드라고 생각된다. 더 좋은 방법이 있는지 공부해야겠다.

💡코드(메모리 : 38092KB, 시간 : 456ms)

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

arr = [True] * (N+1)
arr[0] = False
arr[1] = False
for i in range(2, N+1):
    if arr[i]:
        for j in range(2*i, N+1, i):
            arr[j] = False

for i in range(N+1):
    if arr[i]:
        if M <= i <= N:
            print(i)

💡소요시간 : 2m