에라토스테네스의 체

에라토스테네스의 체

에라토스테네스의 체는 소수 관련 문제를 풀 때 가장 자주 사용되는 방법입니다.

소수란 '양의 약수를 두개만 가지는 자연수' 를 의미합니다. 이러한 소수를 대량으로 빠른 시간 내에 구하는 방법이 에라토스 테네스의 체 입니다.

-지워지지 않는 수를 찾을때는 루트 n까지만 찾습니다. 소수 판정 알고리즘과 동일한 최적화.

- 배수들을 지울 때 i*i에서 시작합니다. 2*i는 이미 2의 배수를 지워졌을때 지워 졌을것 3*i도 마찬가지

코드 ( C++ )

#include <iostream>

#include <cmath>

#include <cstring>

using namespace std;

int n;

// 소수인지 아닌지

// IsPrime[i] = i 가 소수인가?

bool IsPrime[101];

void eratosthenes() {

// 1로 IsPrime 배열 초기화

memset(IsPrime, 1, sizeof(IsPrime));

// 루트 n 까지만 계산

int sqrtn = int(sqrt(n));

// 0과 1은 예외 처리

IsPrime[0] = IsPrime[1] = false;

for (int i = 2; i <= sqrtn; ++i)

// 이 수가 아직 지워지지 않았다면

if (IsPrime[i])

//i의 배수 j들에 대하여 isPrime[j] = false 로 둔다.

// i * i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.

for (int j = i * i; j <= n; j += i)

IsPrime[j] = false;

}

int main()

{

cin >> n;

// 2~ 100까지 소수 판별 해보기

// 소수를 판별하는 IsPrime배열이 갱신된다.

eratosthenes();

for (int i = 2; i <= 100; ++i)

{

if (IsPrime[i])

cout << i << "는 소수입니다." << "\n";

else

cout << i << "는 소수가 아닙니다." << "\n";

}

return 0;

}

참고문헌 : 알고리즘 해결 전략