카테고리 없음

[수학] BOJ 1929 소수 구하기

권멋져 2022. 4. 27. 21:49
https://www.acmicpc.net/problem/1929 
 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

 

- 문제 파악

주어진 두 개의 수 사이의 소수를 출력한다 ( 주어진 두 수 포함)

 

- 정답

#include "bits/stdc++.h"

using namespace std;

int arr[1000005];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= m; i++)
    {
        if (arr[i] > 0) continue;

        for (int j = 2; i * j <= m; j++)
        {
            arr[i * j] = 1;
        }

        if(i >= n && i <= m)
            cout << i << "\n";

    }

}