[C++] BaekJoon 1929 소수 구하기

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

---

소수를 출력하는 문제이지만 다음 문제와 같이 사용자가 직접 범위를 지정하는 경우에는 무조건 2부터 시작하지는 않기에

일반적인 소수 출력으로는 문제를 풀기 쉽지 않다.

 

범위 내 소수를 구하는 방법 중 하나인 에라토스테네스의 체를 이용해 문제를 풀었다.

에라토스테네스의 체

 

코드

#include <iostream>
#include <vector>
using namespace std;

void Eratos(int n, int m) {
    if (n <= 1)
    {
        n = 2; // n이 1 이하일 경우, 최소값 2로 설정
    }

    if (m < 2) {
        cout << "X" << "\n";
        return;
    }

    // 소수 여부를 저장하는 배열
    vector<bool> isPrime(m + 1, true);

    // 0과 1은 소수가 아니므로 false로 설정
    isPrime[0] = isPrime[1] = false;

    // 에라토스테네스의 체 알고리즘 적용
    for (int i = 2; i * i <= m; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= m; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 소수 출력
    for (int i = n; i <= m; i++) {
        if (isPrime[i]) {
            cout << i << "\n";
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); //입출력 시간 단축

    int N, M;
    cin >> N >> M;

    if (N <= M) {
        Eratos(N, M);
    }
    else {
        cout << "유효한 범위를 입력하세요." << "\n"; // endl < \n 코드 실행시간 단축
    }

    return 0;
}

 

설명

에라토스테네스의 체 알고리즘을 구현해 코드를 구성하였다.

N과 M에 각 숫자를 입력하고 이때 N이 M보다 크면 코드를 실행하지 않도록 하였다. 

 

void Eratos(int n, int m) {
    if (n <= 1)
    {
        n = 2; // n이 1 이하일 경우, 최소값 2로 설정
    }

    if (m < 2) {
        cout << "X" << "\n";
        return;
    }

    // 소수 여부를 저장하는 배열
    vector<bool> isPrime(m + 1, true);

    // 0과 1은 소수가 아니므로 false로 설정
    isPrime[0] = isPrime[1] = false;

    // 에라토스테네스의 체 알고리즘 적용
    for (int i = 2; i * i <= m; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= m; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 소수 출력
    for (int i = n; i <= m; i++) {
        if (isPrime[i]) {
            cout << i << "\n";
        }
    }
    cout << "\n";
}

에라토스테네스의 체 알고리즘을 계산하기전 소수는 0과 1을 계산하지 않으므로 n의 값이 2 아래일 경우

n값을 2로 설정하였다.

 

반대로 m의 값이 2보다 작을 경우에는 알고리즘을 실행하지 않고 X를 리턴.

소수가 맞는지 아닌지를 판별해야 하므로 불을 이용한 벡터를 구현, 이때 0과 1은 소수가 아니므로 false

 

알고리즘에서 처음에 입력받은 n값 상관없이 2부터 m까지 알고리즘 진행, 2의 배수부터 시작해 해당하는 숫자는

소수가 아니므로 자기 자신을 제외한 모든 배수를 false로 설정.

 

체 내에서 걸러진 숫자를 범위 내에서 출력