[1929] 소수 구하기 (C++)

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M; cin >> N >> M;
    vector<int> A(M+1);

    for (int i = 2; i <= M; i++)
        A[i] = i;

    for (int i = 2; i <= sqrt(M); i++) {
        if (A[i] == 0)
            continue;

        for (int j = i + i; j <= M; j += i)
            A[j] = 0;
    }

    for (int i = N; i <= M; i++) {
        if (A[i] != 0) cout << A[i] << "\n";
    }

    return 0;
}

 

1. 에라스토테네스의 체를 사용, 범위는 M의 제곱근으로 제한

2. 소수가 아닌 수는 0으로 바꾸고, 출력 시 A[i]의 값이 0이 아닌 경우만 출력

 

 

A[i] = i로 초기화하는 과정에서 int i = 0으로 구현해 틀린 문제