BOJ - 소수(2581)

실버4 : 수학 문제이다.

생각

소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 10000
using namespace std;
int N, M;
bool isPrime[MAX+1];
 
void SeiveofEratosThenes(){
    fill(isPrime+2, isPrime+MAX+1, true);
    for (int i = 2; i*i <= M; i++) {
        if (isPrime[i] == false) continue;
        for (int j = i*i; j <= M; j+=i) {
            isPrime[j] = false;
        }
    }
}
 
int main(){
    cin >> N >> M;
    SeiveofEratosThenes();
 
    vector<int> primeArr; int sum = 0;
    for (int i = N; i <= M; i++) {
        if (isPrime[i]) {
            primeArr.push_back(i);
            sum += i;
        }
    }
    if (primeArr.size() == 0) {
        cout << -1 << '\n';
    } else cout << sum << '\n' << primeArr[0] << '\n';
    return 0;
}

Reference

• 백준(2581번) - 소수