졍's 기술 블로그

소수 구하기

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론,소수 판정, 에라토스테네스의 체

문제

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

입력

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

출력

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

예제 입출력

Algorithm

1. 1부터 N까지 숫자 리스트 생성
2. 2부터 루트 N까지의 숫자로 리스트 내의 숫자를 순차적으로 나누면서 나누어떨어지는 수 Fasle 표시
3. M부터 N까지의 숫자 중 True 값 갖는 숫자만 출력

Code

import math

# 입력
M, N = map(int, input().split())
# 1부터 N까지 숫자 리스트 생성
nums = [True for _ in range(N+1)]
nums[1] = False # 1은 소수가 아니므로 False 저장

# 2부터 루트 N + 1까지의 숫자로 나눔
for i in range(2, int(math.sqrt(N) + 1)):
    # 현재 숫자가 나누어진 적 없다면
    if nums[i]:
        # i * 2부터 N을 넘지 않을 때까지의 숫자를 모두 Fasle로 저장
        j = 2
        while i*j < N+1:
            nums[i*j] = False
            j += 1

answer = ''
for i in range(M, N+1):
    if nums[i]:
        answer += str(i) + '\n'
print(answer)

메모리: 42080 KB
시간: 684 ms