Sieve of Erathosthenes(에라토스테네스의 체)

그리스의 수학자이인 에라토스테네스가 고안한 소수를 찾는 방법으로 특정 양의 정수보다 작은 소수를 찾아내는 방법이다.

자연수 n보다 작은 소수 p를 구하는 방법.
How to)
1. 1을 지우고 p를 2로 놓는다.
2. p를 남기고 n보다 작은 p의 배수를 모두 제거한다.
3. 아직 제거되지 않은 p보다 큰 수 중에서 최소의 수를 다시 p로 놓는다.
4. 다시 2. 로 돌아간다.

프로그래밍 구현 예)
 
#include <iostream>
using namespace std;
int main(void)
{

int i;
            cout << "Input the number : ";                       
            cin >> i;
            while(i)
            {
                        for(j=2;j<=i;j++)
                        {
                                    if(i%j == 0 && i!=j)
                                                break;
                                    if(i==j)
                                    {
                                                cout << "We've found : ";
                                                cout << i << endl;
                                                return 0;
                                    }
                        }
            i++;
            };
}