[수학/소수] 백준 1929 소수 구하기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1929번: 소수 구하기

 

 

 

2. 문제 풀이

 M이상 N이하의 모든 소수를 출력하는 문제입니다.

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 소수판별 알고리즘을 사용하면 쉽게 풀 수 있습니다. 에라토스 테네스의 체를 활용한 소수 판별은 위 글에서 찾아보실 수 있습니다.

 

 

 

3. 코드

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

def isPrime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

for i in range(M, N+1):
    if isPrime(i):
        print(i)

 에라토스 테네스의 체를 사용하지 않고, M부터 N까지 일일이 소수 판별해도 통과합니다.