띠그랭

에라토스테네스의 체 - (소수 구하기)

소수를 구하는 알고리즘 중에 가장 유명한 Algorithm

아리스토텔레스 형의 친구 에라토스테네스의 체이다.

바로 본론으로 들어가서 소스코드 함 봐보자.

그냥 평범하게 2중 for문을 통해 구할 수도 있지만, 구해야 하는 소수의 자릿수가 커지면 시간초과가 떠버릴 것이다.

그래서 간단한 if문을 더해주어 2중 for문이지만, O(N)과 같은 시간복잡도를 낼 수 있다리.

이거는 수학자들에 의해 이미 증명된 공식을 사용한 것인데.

소수는 n의 배수가 아니어야 한다.

입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.

그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

이 소스코드는 1000 이하의 소수를 구하는 놈이다리.

소스 코드

 
x
#include<iostream>
​
using namespace std;
​
int main()
{
    int arr[1001] = {0};
    for(int i=2;i<=1000;i++)
        arr[i] = i;
    for(int i=2;i<=1000;i++)
    {
        if(!arr[i]) continue;
        for(int j = i*2; j <=1000; j+=i)
            arr[j] = 0;
    }
    
    for(int i=2;i<=1000;i++)
    {
        if(arr[i]) cout << arr[i] << ' ';
    }
    
    return 0;
}