[수학] 1929 소수 구하기

멍멍코 2024. 1. 24. 15:42

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

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

www.acmicpc.net

import sys

def eratosthenes(M, N):
    sieve = [True] * (N + 1)
    sieve[0] = sieve[1] = False  # 0과 1은 소수가 아님

    # int()는 내부의 수치가 소수일 경우 내림을 하여 가장 가까운 정수로 변환한다
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, N + 1, i):
                sieve[j] = False

    for i in range(M, N + 1):
        if sieve[i]:
            print(i)

if __name__ == '__main__':
    M, N = map(int, sys.stdin.readline().split())
    eratosthenes(M, N)

저작자표시 (새창열림)