#02. 에라토스테네스의 체(Sieve of Eratosthenes)

• 소수 판정법 중 하나

 

• 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
• 2는 소수이므로 오른쪽에 2를 쓴다.
• 자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
• 자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
• 자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
• 자기 자신을 제외한 7의 배수를 모두 지운다.
• 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

---

#include <stdio.h>

int number = 100000;
int a[1000001];

void primeNumberSieve() {

	// 1. 배열을 생성하여 초기화한다.
	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}

	// 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
	// (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0)
			continue; // 이미 지워진 수라면 건너뛰기

					  // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
		for (int j = 2 * i; j <= number; j += i) {
			a[j] = 0;
		}
	}

	// 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
	for (int i = 2; i <= number; i++) {
		if (a[i] != 0) printf("%d ", a[i]);
	}
}

int main(void) {
	primeNumberSieve();
	return 0;
}

---

 

이 외의 소수 판정법

 

• 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 아니라면 소수로 정의하는 방법

#include <stdio.h> 
#include <string.h> 

int primenumber(int n) { 
	int i; 
	int tmp = 1, count = 0; 
	
	if (n == 1) 
		tmp = 0; 
	for (i = 2; i < n/2; i++) { 
		if (n % i == 0) 
			tmp = 0; 
	} 
	if (tmp == 1) 
		count++; 

	printf("%d\n", count); 
} 

main() { 
	int N, count; 
	int num[100]; 
	
	scanf("%d", &N); 
	for (int i = 0; i < N; i++) { 
		scanf("%d", &num[i]); 
		primenumber(num[i]); 
	} 
}

 

• 해당 숫자의 절반까지만 확인하는 방법

int primenumber(int n) {

	int i;
	for (i = 2; i < n / 2; i++) {
		if (n%i == 0)
			return 1;
	}
	return 0;
}

 

• 해당 숫자의 제곱근까지 확인하는 방법

#include <stdio.h>
#include <math.h>

int isprimenumber(int n) {

	int end = (int)sqrt(n);

	for (int i = 2; i <= end; i++) {
		if (n%i == 0)
			return 1;
	}
	return 0;
}

 

---

※ 참고한 사이트 ※

 

myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

blog.naver.com/ndb796/221233595886

22. 에라토스테네스의 체

velog.io/@max9106/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-%EC%B2%B4

[Algorithm] 에라토스테네스의 체

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전