MODE::CREATIVE

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

BOJ

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

LEE MINGYU 2024. 10. 2. 16:19

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;
}

'BOJ' 카테고리의 다른 글

[백준][c++] 1735번: 분수 합  (2) 2024.10.03
[백준][c++] 1783번: 병든 나이트  (1) 2024.10.03
[백준][c++] 1966번: 프린터 큐  (0) 2024.10.02
[백준][c++] 2108번: 통계학  (2) 2024.10.01
[백준][c++] 2193번: 이친수  (0) 2024.09.22