2.5 KiB
2.5 KiB
deck:: Logseq/coding tip
-
1. 개념 및 동작방식
- 특정 범위(
N) 내의 **모든 소수(Prime Number)**를 가장 빠르고 효율적으로 찾아내는 알고리즘 - 동작방식
-
2 부터 $N$까지의 모든 수를 나열한다. id:: 694bddc6-b2c6-4273-b710-22d9fff534c2 아직 지워지지 않은 수 중 가장 작은 수(
P)를 찾는다.그 수는 소수이다. $P$를 제외한 $P$의 배수들을 모두 지운다. 위 과정을 {{cloze $N$의 제곱근(\sqrt{N})}}에 도달할 때까지 반복한다. #card #+BEGIN_EXTRA합성수 $N$이 $A \times B$일 때, $A$와
B중 적어도 하나는 반드시\sqrt{N}이하 이기 때문이다. 그리고 각 배수를 지우는 로직 특성상 대칭되는 약수들도 미리 지워지게 된다. 따라서 그 범위 내에서 나누어 떨어지는 수가 없다면 그 수는 소수이다. #+END_EXTRA
-
- 특정 범위(
-
2. 코드(C언어 기준)
- 기본 구성
id:: 694bdf77-1c51-45a0-91ce-988de1542b9f
void sieve_of_eratosthenes(int n)를 정의하면? #card#include <stdio.h> #include <stdbool.h> #include <math.h> #define MAX_N 1000 // true: 소수, false: 소수 아님 bool is_prime[MAX_N + 1]; void sieve_of_eratosthenes(int n); int main() { int n = 100; // 100까지의 소수 구하기 sieve_of_eratosthenes(n); printf("Primes up to %d:\n", n); for (int i = 2; i <= n; i++) { if (is_prime[i]) { printf("%d ", i); } } printf("\n"); return 0; }-
void sieve_of_eratosthenes(int n) { // 1. 초기화: 모든 수를 소수(true)로 가정 // 0과 1은 소수가 아니므로 false로 설정 is_prime[0] = false; is_prime[1] = false; for (int i = 2; i <= n; i++) { is_prime[i] = true; } // 2. 체로 거르기 (핵심 로직) // i*i <= n 조건: n의 제곱근까지만 검사하면 충분함 (최적화) for (int i = 2; i * i <= n; i++) { // i가 소수라면 (아직 지워지지 않았다면) if (is_prime[i]) { // i의 배수들을 모두 지움 (false로 설정) // j = i * i 부터 시작: i*2, i*3 등은 이미 이전 단계(2, 3...)에서 지워졌으므로 생략 가능 (최적화) for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } }
-
- 기본 구성
id:: 694bdf77-1c51-45a0-91ce-988de1542b9f