[C++] 백준 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을 출력한다.

 

 

예제 입력 1

60
100

예제 출력 1

620
61

예제 입력 2

64
65

예제 출력 2

-1

 

 

해결 아이디어

백준 1978번 / 소수 찾기 / C++

이전 글에서 다룬 소수 찾기와 같은 알고리즘을 공유하고 찾은 소수들을 저장하는 벡터 컨테이너를 사용하여 min부터 max까지 반복하며 저장한 소수들의 합을 출력한다. min부터 max까지 순차적으로 반복하기에 p에 데이터가 있다면 p[0]의 값이 최소값이기에 출력하면 조건에 부합한다.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int min, max, s = 0;
    vector<int> p;
 
    cin >> min >> max;
 
    for (int i = min; i <= max; ++i)
    {
        if (i < 2) continue;
 
        bool isP = true;
 
        for (int j = 2; j * j <= i; ++j)
        {
            if (i % j == 0)
            {
                isP = false;
                break;
            }
        }
 
        if (isP)
        {
            p.push_back(i);
        }
    }
 
    for (int i = 0; i < p.size(); ++i)
    {
        s += p[i];
    }
 
    if (p.size())
    {
        cout << s << endl << p[0];
    }
    else
    {
        cout << -1;
    }
 
}