백준 2581 번 문제 풀이 C++ :소수

#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.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  int i, j, M, N, sum = 0, min, so;

  cin >> M; // 시작값 M 을 입력받아 정수형으로 대입
  cin >> N; // 끝값  N 을 입력받아 정수형으로 대입
  sum = 0; // 소수의 합을 저장할 변수
  min = N; // 소수중 최솟값을 저장할 변수, 초기값으로 최대값을 넣어둔다.
  for(i = M; i <= N; i++) { // 숫자에서 M이상 N이하 i 값으로 루프
    so = 1; // 소수확인용 변수
    if(i == 1) so = 0; // 1은 소수가 아니므로 별도 처리.
    for(j = 2; j < i; j++) { // 2부터 i-1까지 j로 전달하고 루프
      if(i % j == 0) { // 다른 수로 나누어 떨어지면 소수가 아님
        so = 0; // 소수가 아님
        break; // 소수가 아니므로 확인 중지
      }
    }
    if(so == 1) { // 소수이면 
      sum += i; // 소수의 합 계산
      if(min > i) min = i; // 최솟값 체크
    }
  }

  if(sum == 0) cout << -1; // 총합이 없다는 것은 소수가 없다는 의미. -1 출력.
  else cout << sum << endl << min; // 소수 총합, 최솟값 출력
  return 0;
}