[C++] BAEKJOON (2581) 소수

문제

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

 

첫째 줄에 M, 둘째 줄에 N이 주어지며, 두 수는 자연수이다. (M, N ≤ 10,000)

 

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

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

 

예. M = 60, N = 100

60 이상 100 이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97이다.

소수의 합은 61 + 67 + 71 + 73 + 79 + 83 + 89 + 97 = 620이고, 최솟값은 61이다.

 

결과

#include <iostream>

int  main() {
    using namespace std;

    int M, N, cnt = 0;   // 소수의 개수 cnt 0으로 초기화한다.
    cin >> M >> N;

    int sum = 0;   // 소수의 합계 0으로 초기화한다.
    int min = N;   // 최솟값 min을 M과 N의 입력값 중 큰 수 N으로 초기화한다. (M이 소수가 아닐 수 있기 때문이다.)

    for (int num = M; num <= N; ++num) {
        if (num == 2) {   // 2는 소수이다.
            ++cnt;
            sum += num;
            min = num;
        }
        else if (num > 2) {   // 1은 소수가 아니며, 2부터 나누어 준다.
            for (int j = 2; j < num; ++j) {
                if (num % j == 0) {
                    break;
                }

                if (j == num - 1) {   // 소수는 약수로 '1'과 '해당 숫자'만 가지고 있는 숫자이므로, '해당 숫자-1'까지 도달하면 소수이다.
                    ++cnt;
                    sum += num;
                    if (num < min) {   // 최솟값 min이 해당 숫자보다 작다면 최솟값이 된다.
                        min = num;
                    }
                }
            }
        }
    }

    if (cnt == 0) {     // 소수의 개수가 0이면,
        cout << "-1";   // '-1'을 출력한다.
    }
    else {
        cout << sum << '\n' << min;
    }

    return 0;
}

 

 

 

 

출처: BAEKJOON