[Silver III] 소수 구하기 - 1929

문제 링크

성능 요약

메모리: 48592 KB, 시간: 216 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 12월 19일 16:02:04

문제 설명

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

입력

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

출력

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

import math


def prime(x, y):
    arr = [False, False] + [True] * (y-1)

    for i in range(2, int(math.sqrt(y)) + 1):
        if arr[i]:
            for j in range(2*i, y+1, i):
                arr[j] = False
    return arr

m, n = map(int, input().split())
result = prime(m, n)
for i in range(m, n+1):
    if result[i]:
        print(i)

풀이

이 문제는 에라토스테네스의 체를 사용하여 풀이를 해도 된다.

prime함수는 0을 포함한 n까지 True를 통해 리스트를 초기화해 준다. 여기서 0과 1은 소수가 아니므로 False로 초기화한다.

소수를 판별하는 알고리즘과 같이 2부터 n까지 반복하며 해당 인덱스가 True이면 해당 숫자의 배수를 모두 False로 한다.

이를 모두 수행하고 소수 리스트를 반환해주고 출력해주면 된다.

다른 풀이로는 다음 소수 문제처럼 풀이해주면 된다.

import math


def prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True


m, n = map(int, input().split())
for i in range(m, n+1):
    if prime(i):
        print(i)