백준 2581번 : 소수

https://www.acmicpc.net/problem/2581

1. 문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다.

2. 알고리즘

소수의 합을 저장 할 SUM 이라는 변수를 선언한다.

소수 판별을 하여 소수이면 SUM 에 적산 한다.

소수 중 가장 작은 값을 찾기 위해 CAND 라는 변수를 선언 하고 987654321 로 초기화 한다.

소수 판별을 하여 소수이면 CAND 보다 작다면 CAND 를 현재 값으로 치환한다.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
 
int prime(int n){
 
    if (n == 1) {
        return 0;
    }
    
    if (n == 2) {
        return 1;
    }
 
    for(int i=2;i<n;i++) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}
 
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m; cin >> n >> m;
 
    int sol = 0;
    int cand = 987654321;
    for (int i = n; i<=m; i++) {
        if (prime(i)) {
            sol += i;
            cand = min(cand, i);
        }
    }
 
    if (sol) {
        cout << sol << "\n";
        cout << cand << "\n";
    } else {
        cout << -1 << "\n";
    }
    
    return 0;
}