[C++] 백준 BOJ 1929 소수 구하기

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

BOJ 2581 소수 문제랑 완전 동일한 문제라고 할 수 있다.

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

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

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

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

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

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

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

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

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

// BOJ 1929 소수 구하기
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int M, N;
    cin >> M >> N;
    vector<bool> isPrime(N + 1, true); // 소수 리스트
    bool chk = false;
 
    // 에라토스테네스의 체 이용하여 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])
            cout << i << '\n';
 
    return 0;
}