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

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

1929번: 소수 구하기

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main()
{
    int M, N;
    int arr[1000001]{ 0, };
    cin >> M >> N;

    for (int i = 2; i <= N; i++)
    {
        arr[i] = i;
    }

    for (int i = 2; i * i <= N; i++)
    {
        if (arr[i] == 0)
        {
            continue;
        }
        for (int j = i * i; j <= N; j += i)
        {
            arr[j] = 0;
        }
    }

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

마무리 : 소수 구하기 문제는 에라토스테네스의 체를 이용하여 소수를 찾는다. 숫자들이 있으면 1을 제거해주고 2의 배수, 3의 배수 제거하는 식으로 남은 숫자 즉, 소수를 출력할 수 있게 된다.