백준BOJ/Python : 1929번 소수 구하기

1929번 : 소수 구하기 원본

알고리즘 분류

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

문제

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

입력

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

출력

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

풀이

소수 : 1보다 큰 자연수 중 1과 자기 자신으로만 나눠지는 수 에라토스테네스의 체 : 에라토스테네스가 발견한 소수 찾는 방법 @gif[https://static.blex.me/images/content/2023/4/17/202341722_ziTKAcQgUjDtgJw1z5g8.mp4]

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
2. 2는 소수이므로 2를 넣고, 2를 제외한 2의 배수를 모두 지움
3. 남아있는 수 중 3도 소수이므로 3을 소수에 넣고 3을 제외한 3의 배수를 모두 지움
4. 3 과정을 반복하면 원하는 구간의 소수를 찾을 수 있음
5. 2부터 120까지 소수를 구할 경우 120보다 큰 수의 제곱근을 갖는 자연수는 11(11^2 = 121)이므로, 11보다 작은 자연수까지 과정을 반복하면 됨

소스 코드

Python 1

• 에라토스테네스의 체 방식을 이용한 소수 구하기
• 전체를 구하는 방식 O(N)

import sys

input = sys.stdin.readline
minNum, maxNum = map(int, input().split())
ListNum = [True] * (maxNum+1)
ListNum[0] = False
ListNum[1] = False

for i in range(2, int(maxNum**0.5) + 1):
    if ListNum[i]:
        for j in range(i*2, maxNum+1, i):
            ListNum[j] = False

for i in range(minNum, maxNum+1):
    if ListNum[i]:
        print(i)

Python 2

• 약수가 존재 여부를 확인해 소수를 찾는 방법

import math
import sys

input = sys.stdin.readline

def is_prime(parse_int):
    if parse_int == 1:
        return False

    sqrt = int(math.sqrt(parse_int))

    for i in range(2, sqrt+1):
        if parse_int % i == 0:
            return False

    return True

min_num, max_num = map(int, input().split())

for i in range(min_num, max_num+1):
    if is_prime(i) == True:
        print(i)

참고

에라토스테네스의 체, 위키백과