소수판별(2) 에라토스테네스의 체(C언어)

간단히 말하면 어떤 수 x까지 소수인지 합성수인지 체(배열)에다 저장하는 것입니다.

메모리와 시간만 충분하다면 선형시간에 소수인지를 판단할 수 있습니다.

먼저 예를들어 x가 10일때 를 보면

int arr[11];
for(int i=2; i<=10;i++){
   arr[i]=i;
}

첫번째줄에서 배열 arr[11]을 선언해서 0부터 10까지의 인덱스를 가지는 배열을 만들어 줍니다.

두번째줄에서 for문을 통해 i(인덱스 번호)를 2부터 시작해서 10까지 자기자신의 인덱스 번호를 value값으로 가지게

만들어 줍니다.

       0         1             2           3          4             5          6             7            8         9         10

0

0

2

3

4

5

6

7

8

9

10

 

for (int i = 0; i <= x; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i + i; j <= x; j += i) {
			arr[j] = 0;
		}
}

그 다음에는 2부터 소수이므로 2를 제외하고 2의 배수 인덱스의 value값을 0으로 만들어 줍니다. 

2가 소수 이므로 2의 배수는 2로 나누어 떨어지기 때문에 합성수 입니다. ex) 4, 6, 8, 10........

2의 배수의 인덱스 value값을 0으로 만든후 그다음  3을 제외한 3의 배수의 인덱스 value값을 0으로 만들어 줍니다.

ex) 6, 9..... 여기서 6은 아까 2의 배수이므로 이미 value값(arr[6]=0)이 0이므로 continue를 사용해 넘어가 줍니다.

이것을 반복하면 배열 값이 다음과 같이 초기화 됨을 알 수 있습니다.

       0         1             2           3          4             5          6             7            8         9         10

0

0

2

3

0

5

0

7

0

0

0

따라서 0이 아닌 값은 소수이고 0인값은 합성수가 됩니다. 0인 아닌 값 즉, 소수인 값만 출력!  코드는 다음과 같습니다.

for (int i = 2; i <= x; i++) {
		if (arr[i] != 0)
			printf("%d ", arr[i]);
}

전체 코드를 보면 다음과 같습니다.

#include<stdio.h>
int arr[11];
void primeNumberSieve(int x) { //에라토스테네스의 체
	for (int i = 2; i <= x; i++) {
		arr[i] = i;
	}
	for (int i = 0; i <= x; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i + i; j <= x; j += i) {
			arr[j] = 0;
		}
	}
	for (int i = 2; i <= x; i++) {
		if (arr[i] != 0)
			printf("%d ", arr[i]);
	}
}
int main(){
    int x;
    scanf("%d",&n);
    primeNumberSieve(x);
    
    return 0;
}

풀어볼만한 문제