백준 2581번 파이썬 풀이: 소수

백준 2581번 소수

 

알고리즘 분류: 수학, 정수론, 소수 판정

 

링크: https://www.acmicpc.net/problem/2581

 

2581번: 소수

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

문제 파악

 

문제 자체는 간단하다.

 

m이상 n이하의 수중에서 소수인 것들을 모두찾아 이들의 합과 제일 작은 수를 출력하는 문제이다.

 

만약 소수가 없을 경우에는 -1을 출력하면된다.

 

소수의 정의는 1보다 큰 자연수 중에서 약수가 1과 자기 자신뿐인 수를 말한다.

 

1은 소수에 포함되지 않는다는 점을 확인하고 문제를 풀면 된다.

 

 

코드

# 2581번

m = int(input())
n = int(input())

prime = []

for i in range(m, n + 1):
    check_prime = True

    for j in range(2, i):
        if i % j == 0:
            check_prime = False
            break
    if i == 1:
        check_prime = False

    if check_prime == True:
        prime.append(i)

prime_sum = 0
for i in range(len(prime)):
    prime_sum += prime[i]

if len(prime) < 1:
    print(-1)
else:
    print(prime_sum)
    print(prime[0])

m이상 n이하의 수 중에서 소수를 찾는 문제이기 때문에 for문의 range를 m, n+1로 설정해준다.

 

check_prime이라는 불린값을 가지는 변수를 만들어 소수이면 True 소수가 아니면 False를 나타내게한다.

 

만약 m이상 n이하의 수중에서 1과 자기 자신을 제외하고 약수가 있다면 그 수는 소수가 아니기 때문에

 

check_prime에 False를 넣어주고 반복문을 빠져나오게 한다.

 

check_prime이 True를 나타내는 값들만 prime이라는 리스트에 담아둔다.

 

이 때 m이상 n이하의 수중에서 1이 들어간다면 1은 check_prime이 False를 나타내게한다.

 

반복문이 끝났다면 prime안에 모든 수들을 더해서 prime_sum에 담아준다.

 

prime의 리스트 길이가 1이상이라면 소수가 있다는 뜻이므로 prime_sum과 제일 작은 소수를 출력해주고

 

그렇지 않으면 소수가 없다는 뜻이므로 -1을 출력해준다.