에라토스테네스의 체

'에라토스테네스의 체'는 수학에서 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 소수는 1과 자기 자신으로밖에 자신을 나눌 수 없는 수이다.

어떤 수 N이 소수인지 판별하기 위해서 사용하는 방법은 다음과 같다. 2부터 N의 제곱근까지의 수 중 단 하나라도 N을 나눌 수 없다면 N은 소수이다. 예를 들어 16이 소수인지 확인하려면 2부터 4까지의 수로 나눠보는 작업을 거치면 된다. 나눌 수 없었다면 소수이다.

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int N, rt;
    cin >> N;

    if (N == 1)
        cout << "소수가 아닙니다.\n";
    else if (N == 2 || N == 3)
        cout << "소수입니다.\n";
    else
    {
        for (int i = 2; i <= sqrt(N); i++)
        {
            if (N % i == 0)
            {
                cout << "소수가 아닙니다.\n";
                break;
            }
            if (i == (int)sqrt(N))
                cout << "소수입니다.\n";
        }
    }

    return 0;
}