[C++] 백준 BOJ 2581 소수

문제 링크 : https://boj.kr/2581

소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.

소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.

자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.

하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.

하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.

어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이다.

소수 리스트를 구하는 방법은 에라토스테네스의 체를 이용하여 구하였다.

미리 구해둔 소수 리스트를 통해서 소수인지 아닌지를 판별하면 더 빨리 구할 수 있다.

또다른 방법으로는 N의 제곱근까지만 소수 리스트를 구해서 그 소수 리스트들에 있는 숫자로 자기 자신이 나누어 떨어질 수 있는가만 구해도 된다.

// BOJ 2581 소수
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int M, N;
    cin >> M >> N;
    vector<bool> isPrime(N + 1, true); // 소수 리스트
    bool chk = false;
    int minPrime;
    int sum = 0;
 
    // 에라토스테네스의 체 이용하여 N까지의 소수 구하기
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            // 소수의 N배수들은 모두 소수가 아님
            for (int j = 2 * i; j <= N; j += i)
                isPrime[j] = false;
        }
    }
 
    for (int i = M; i <= N; i++) {
        if (isPrime[i]) {
            if (!chk) { // 첫 소수 체크
                chk = true;
                minPrime = i;
            }
            sum += i;
        }
    }
 
    if (chk)
        cout << sum << '\n' << minPrime;
    else // N~M에서 소수가 하나도 발견되지 않았으면
        cout << "-1";
 
    return 0;
}