백준 2581 번 문제 풀이 Python 파이썬 :소수

#65. 백준 2581번 문제 풀이: 소수

자연수 M이상 N이하의 자연수 중 소수에서 이들의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=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을 출력한다.

입력/출력

--입력--
60
100
--출력--
620
61
--입력--
64
65
--출력--
-1

문제풀이+해설

소수는 1과 자신의 수 외에는 나누어지지 않는 1보다 큰 정수를 말한다. 예를 들어, 2, 3, 5, 7 ...
어떤 수가 소수 여부를 판단하려면, 2부터 자신보다 작은 수 까지 %(나머지) 연산을 해서 0으로 떨어지면 나누어지는 수가 있으므로 소수가 아니다.

주어진 범위에 해당하는 자연수를 확인해서 소수를 찾아내고, 
루프를 돌려서 합을 계산함과 동시에 최솟값을 찾으면 된다.

code sol.

코드편집/실행

M = int(input())
N = int(input()) # 숫자 M, N 을 입력받아 정수형으로 대입
sum = 0 # 소수의 합을 저장할 변수
min = N # 소수중 최솟값을 저장할 변수, 초기값으로 최대값을 넣어둔다.
for n in range(M, N+1): # 숫자에서 M이상 N이하 순서대로 n에 넘겨주며 루프
  so = True # 소수확인용 변수
  if n == 1: so = False # 1은 소수가 아니므로 별도 처리.
  for i in range(2, n): # 2부터 n-1까지 i로 전달하고 루프
    if n % i == 0: # 다른 수로 나누어 떨어지면 소수가 아님
      so = False # 소수가 아님
      break # 소수가 아니므로 확인 중지
  if so == True: # 소수이면 
    sum += n # 소수의 합 계산
    if min > n: min = n # 최솟값 체크

if sum == 0: print(-1) # 총합이 없다는 것은 소수가 없다는 의미. -1 출력.
else: print(sum, min, sep = "\n") # 소수 총합, 최솟값 출력