에라토스테네스의 체

에라토스테네스의 체란 소수를 판별할 때 쓰이는 알고리즘이다.

소수란 1과 자기자신 외에는 약수가 없는 수를 뜻한다.

 

이 소수를 구하기 위해 배열을 사용한다. 배열은 index에 해당하는 수가 소수인지를 true / false로 구분하는 배열이다.

일단 배열의 모든 값을 true로 초기화한다.

그 후 1은 소수가 아니니까 false로한다.

 

그 다음 두번의 for문을 통해 모든 수를 판별한다.

 

첫번째 for문은 2부터 sqrt(N)까지 반복한다. sqrt(N) 부터 N 까지의 수는 자동으로 판별이 되기때문에 N까지 반복하지 않아도 된다. 이 때 sqrt(N)을 구하려면 사전에 루트를 구해야하고 헤더도 포함하는 귀찮음이 있으니 이를 해결하기위해 꼼수를 사용한다. i*i<=N으로 조건식을 걸면 된다. 2부터 sqrt(N)까지 isPrime[i]가 false라면 이미 소수가 아니라는 뜻이기때문에 continue로 다음 수를 조사하고 true라면 소수라는 뜻이므로 두번째 for문을 실행한다.

 

두번째 for문은 해당 소수를 제외한 수부터 N까지 모든 배수를 false로 바꾼다. 예를들어 2가 소수이기때문에 2의 배수는 모두 소수가 아닐것이다. 따라서 4,6,8,10, ... 에 해당하는 모든 짝수를 false로 바꿔주는 것이다.

 

이 두 for문을 사용하면 소수여부를 쉽고 빠르게 판단할 수 있다.

 

---

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
bool isPrime[1000000];

void eratosthenes()
{
	//1은 소수가 아니다.
	isPrime[1] = false;
	for (int i = 2; i * i < 1000000; i++) {
		if (isPrime[i] == false) continue;
		for (int j = i+i; j < 1000000; j += i) {
			isPrime[j] = false;
		}
	}
	return;
}

int main()
{
	memset(isPrime, true, sizeof(isPrime));
	eratosthenes();
	for (int i = 0; i < 100; i++)
		cout << i << " is Prime Number? " << isPrime[i] << endl;

	return 0;
}