파이썬 소수(백준 BOJ 2581)
2022, Jul 19
문제
자연수 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을 출력한다.
예제 입력 1
60
100
예제 출력 1
620
61
예제 입력 2
64
65
예제 출력 2
-1
📝 풀어보기
📌 이 문제는 앞선 소수 찾기(BOJ 1978)와 풀이 방법이 유사하다.
최소값과 최대값을 입력받을 변수 M, N과 M - N 범위 내의 소수를 담을 리스트 A, 합계를 담을 변수 B를 선언한다.
M = int(input()) # 최소값
N = int(input()) # 최대값
A = [] # 범위 내의 소수를 담을 리스트
B = 0 # 합계를 담을 변수
📌 에라토스테네스의 체 방식으로 최대값+1 범위에서 최대값의 제곱근까지만 탐색하며 소수를 가져온다. 도출된 소수가 최소값인 M보다 작은 경우에는 삽입하지 않는다.
# 에라토스테네스의 체
for i in range(2, N+1): # 2부터 최대값+1의 범위까지
check = True
for j in range(2, int((i**0.5)+1)): # 최대값의 제곱근까지만 탐색
if i%j == 0:
check = False
if check:
if i >= M: # 도출된 소수가 최소값인 M보다 클 경우에만 삽입
A.append(i)
📌 소수가 삽입된 리스트 A에서 누적값을 도출한다. 리스트가 비어있지 않은 경우에 리스트의 합과 리스트 내의 최소 숫자를 출력하고 비어있는 경우에 -1을 출력한다.
for k in range(len(A)): # 리스트 A의 합계
B += A[k]
if A != []: # 리스트가 비어있지 않을 경우
print(B)
print(A[0])
else: # 비어있는 경우
print(-1)
전체 코드
M = int(input()) # 최소값
N = int(input()) # 최대값
A = [] # 범위 내의 소수를 담을 리스트
B = 0 # 합계를 담을 변수
# 에라토스테네스의 체
for i in range(2, N+1): # 2부터 최대값+1의 범위까지
check = True
for j in range(2, int((i**0.5)+1)): # 최대값의 제곱근까지만 탐색
if i%j == 0:
check = False
if check:
if i >= M: # 도출된 소수가 최소값인 M보다 클 경우에만 삽입
A.append(i)
for k in range(len(A)): # 리스트 A의 합계
B += A[k]
if A != []: # 리스트가 비어있지 않을 경우
print(B)
print(A[0])
else: # 비어있는 경우
print(-1)