에라토스테네스의 체 Sieve of Eratosthenes

소수 Prime number

---

양의 약수로 1과 자기 자신만을 가지는 자연수

따라서 1은 소수가 아님

 

 

 

 

 

 

에라토스테네스의 체

---

소수를 찾는 방법. 2부터 어디까지~의 소수를 구하는 데 편리함

물론 몇 번째 소수를 구하시오 등등의 문제.. 어쨌든 소수를 구하는 데 좋다.

 

아이디어? 

소수가 아닌 수를 지워나가므로써 소수만을 남게 한다. (소수 아닌 숫자를 걸러주는 체)

 

 

 

위 그림을 보면서 설명하면,

2는 소수다->2의 배수들은 소수 아니므로 걸러냄->3 확인해보니 소수다->3의 배수들은 소수 아니므로 걸러냄->4는 아까 걸러졌으므로 5 확인->..... 반복

 

노가다로 코드짜면 나올 것 같다.

근데 수학적으로 나타내어진 공식이 있다. 덕분에 실행시간을 훨씬 줄일 수 있다. ▼▼▼

 

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

if ((입력받은 수 input%입력받은 수보다 작은 어떤 수 n) == 0)

입력받은 수 input는 소수가 아니다.

하지만 모두 나누어볼 필요는 없고 √n 까지 나누어보았을 때 나눠떨어지면 소수가 아니다.

 

왜??

입력받은 수 input이 소수일 때, input이 input의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 

예를 들어 

4(√4 = 2)는

몫1 나머지4(반대도 가능) 또는 몫2 나머지2 로 나타낼 수 있는데, 

몫과 나머지 둘 중 하나는 무조건!!! √4 인 2 이하이다.

이것을 다시 정리해서 일반적으로 말하면..

어떤 수 N의 몫과 나머지 둘 중 하나는 √N 이하이다.

따라서 2, 3.. √N까지 나누었을 때 나누어떨어지면 소수가 아니다.

 

 

이것을 코드로 나타내면 (입력받은 값까지의 소수를 출력한다.)

#include <iostream>
using namespace std;
void Eratos(int n)
{
	bool* PrimeArray = new bool[n + 1]; //n+1개의 배열 동적할당

	if (n <= 1){ //1보다 작은 수가 들어왔을 해당 범위 내의 소수가 없다
		return;
	}

	for (int i = 0; i <= n; i++) PrimeArray[i] = true;   //모든 배열이 소수라고 가정
	PrimeArray[0] = false; PrimeArray[1] = false;   //0,1은 소수 아니므로 false. 배열의 인덱스 값이 숫자를 나타냄

	for (int i = 2; (i*i) <= n; i++){   //(i*i) <= n 는 i<=√n 을 의미한다
		if (PrimeArray[i]){  //만약 소수라면?
			for (int j = i*i; j <= n; j += i) {   //i 이후 i 배수는 모두 약수를 가진 것이므로 걸러줘야 한다. 
				PrimeArray[j] = false;
			}
		}
	}

	for (int i = 2; i <= n; i++){
		if (PrimeArray[i]) cout << i << endl;
	}
}
int main(){
	while (1){
		int n;
		cout << "어디까지의 소수를 구할까요?: ";
		cin >> n;
		cout << "**********  2~입력값 사이의 소수를 출력합니다" << endl;
		Eratos(n);
	}
	return 0;
}

 

 

 

 

결과 화면!