[기본문제풀이] 에라토스테네스의 체

 

풀이 일시 : 2020-08-13

​

에라토스테네스의 체 :

소수(prime number) 판별 알고리즘이다.

어떤 수로도 나뉘어지지 않아야 되기 때문에 그 수를 나눠보면서 판단할 수 있다..

-> 이 방법은 O(N)의 복잡도를 갖는다. 모든 수를 체크했기 때문이다.

제곱근까지만 약수의 여부를 검증한다

-> 이 방법은 O(N^(1/2))로 계산이 가능하다.

-> int end = (int)sqrt(x)로 두고 x의 소수를 구하려면 2~end까지 체크한다.

​

문제 :

에라토스테네스의 체를 이용하여 소수를 출력하여라.

​

풀이 :

1. 이차원 배열을 생성하여 값을 초기화한다.

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자신은 지우지않는다.)

3. 3의 배수도 지운다. (자신은 지우지 않고 이미 지운경우는 건너뛴다.)

4. 남아있는 숫자들을 출력한다. (소수를 출력)

​

#include <stdio.h>

int number = 100000;
int a[100001];

void primeNumberSieve() {
	for (int i = 2; i <= number; i++) {
		a[i] = i; //배열을 다 초기화해준다.
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue; //이미 방문했던곳은 방문하지않는다.
		for (int j = i+i; j <= number; j += i) { //배수
			a[j] = 0; //방문처리
		}
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] != 0) //0으로 변하지 않은 남은 소수부분 출력
			printf("%d ", a[i]);
	}
}
int main() {
	primeNumberSieve();
}