[기본 알고리즘] 소수 찾기

소수(Prime Number)란?

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 1은 1보다 큰 자연수가 아니기 때문에 소수가 아니다.

예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

 

에라토스테네스의 체

2부터 n까지의 소수들을 찾는다.

2부터 ~ n의 제곱근까지 수들의 배수들을 제외하는 과정을 반복한다.

O(N^1/2)의 시간복잡도를 갖는다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    // 1 ~ 100 사이의 모든 소수 찾기
    int max = 100;

    vector<int> v;
    v.push_back(0);
    v.push_back(0);
    for (int i = 2; i <= max; i++)
    {
        v.push_back(i);
    }

    // 소수 찾기
    for (int i = 2; i < sqrt(max); i++)
    {
        if (v[i] == 0)
            continue;

        for (int j = 2 * i; j <= max; j += i)
        {
            v[j] = 0;
        }
    }

    // 찾은 소수를 출력
    for (int i = 1; i <= max; i++)
    {
        if (v[i] != 0)
        {
            cout << v[i] << ", ";
        }
    }
    cout << endl;
}

 

주요 코드

sqrt()

제곱근을 구하는 함수

제곱근이란, 어떤 수의 제곱근은 제곱하여 그 수가 되는 수이다.