[백준][c++] 1929번: 소수 구하기

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

문제 해석

• 에라토스테네스의 체를 이용해 소수 구하기

알고리즘 분류

• 수학
• 정수론

풀이

• 에라토스테네스의 체를 이용해 N까지의 소수를 판별한다

코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath> 
#include <algorithm>
#include <queue>
using namespace std;

int m, n;
int arr[1000001] = {0,};

int main() { 
    cin >> m >> n;
    arr[0] = 1; //소수가 아님
    arr[1] = 1;

    for (int i=2; i<n+1; i++) {
        for (int j = 2*i; j < n+1; j+=i) {
            if (arr[j] == 0) arr[j] = 1; //소수가 아님
        }
    }

    for(int i = m; i <= n; i++) {
        if(arr[i] == 0) cout << i << "\n";
    }
    return 0;
}