[수학/소수] 백준 2581 소수 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2581번: 소수

 

 

 

2. 문제 풀이

 자연수 M이상 N이하의 소수들의 합과 최솟값을 구하는 문제입니다. 소수가 없을 경우에는 -1를 출력합니다.

 

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

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

 소수판별 알고리즘을 사용합니다. 위 링크를 참조해주세요.

 

 

 

3. 코드

M = int(input())
N = int(input())

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

prime = []
for i in range(M, N+1):
    if isPrime(i):
        prime.append(i)
if len(prime) == 0:
    print(-1)
else:
    print(sum(prime))
    print(min(prime))

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