C++ 소수 찾기, 검사하기 [에라토스테네스의 체]

C++ 소수 찾기, 검사하기 [에라토스테네스의 체] 하는 방법

 

 

 

 

소수 찾는 알고리즘 [에라토스테네스의 체]

 

 

- 2부터 지정한 수까지의 소수들을 찾을 수 있다.

 

-  i(=2)부터 ~ 지정한 수의 제곱근까지 수들의 배수들을 제외하는 과정을 반복하면서 소수를 판별한다. 

( 어느 수의 배수라는 것은 소수가 아니라는 의미)

 

 

 

 

 

->  참조

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

 

 

 

[ 코 드 ]

#include <iostream>
#include <math.h>
#define N 500
#define N2 199
using namespace std;

bool sosu(int n) {
	int k = (int)sqrt(n);
	for (int i = 2; i <= k; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

int main() {
	bool* b = new bool[N + 1];	// 숫자 A을 배열의 A번에 저장하기 위하여 크기 N+1
	for (int i = 2; i < N+1; i++) b[i] = true;
	
	for (int i = 2; i * i < N+1; i++) {
		for (int k = i * i; k < N+1; k += i) {
			b[k] = false;
		}
	}

	// 결과
	cout << N << "까지의 소수들\n";
	for (int i = 2; i < N + 1; i++) if (b[i]) cout << i << ", ";

	cout << "\n\n" << N2 << "는 ";
	if (sosu(N2)) cout << "소수입니다.\n";
	else cout << "소수가 아닙니다.\n";

	return 0;
}

 

 

16~23 라인 : N+1만큼의 크기를 갖는 bool 배열을 선언하고 true로 초기화 해준다. 그리고 N까지 i의 배수들을 false로 바꾸는 과정을 반복한다.

 

 

 

7라인 : sosu함수는 인수로 받은 수가 소수인지 판별하여서 참이면 true를 거짓이면 false를 리턴한다.

 

8라인 : sqrt(n) 함수는 제곱근을 구하는 함수로서 #include <math.h> 를 해주어야 한다.

 

9라인 : for문을 보면 2부터 n의 제곱근인 k까지 검사한다. k까지만 검사해도 되는 이유는

 

ex) n = 16 일 때, k= 4

그러면  "4이전 i=2일 때 검사한 것 "  =  "4이후 i=8일 때 검사한 것"

즉, 2 x 8 = 8 x 2 이므로 제곱근인 k까지만 검사해주면 된다.

 

 

 

 

 

[ 결 과 ]

 

 

결과를 보면 2부터 500전까지의 소수들을 출력한다.

 

또한, 199가 소수인지 아닌지 판별한다.