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

핵심 인사이트 (3줄 요약)

1. 본질: 에라토스테네스의 체는 작은 수의 배수를 지워 소수를 찾는 알고리즘이다.
2. 가치: 단순하면서도 빠르게 소수 목록을 만들 수 있다.
3. 판단: 수를 하나씩 나눠보는 것보다 훨씬 효율적이다.

Ⅰ. 개요 및 필요성

소수를 찾는 가장 대표적인 방법 중 하나다.

배수를 지워 가며 소수를 남긴다.

• 📢 섹션 요약 비유: 합격자만 남기고 나머지를 지우는 명단 정리다.

Ⅱ. 아키텍처 및 핵심 원리

Start with numbers
  ↓ eliminate multiples
Primes remain

작은 소수의 배수를 지워 가면 소수만 남는다. 이 방식이 체(sieve)다.

• 📢 섹션 요약 비유: 구멍 난 체로 걸러내는 것이다.

Ⅲ. 비교 및 연결

에라토스테네스의 체는 소수 판정의 기본 알고리즘이다.

• 📢 섹션 요약 비유: 남는 사람만 골라내는 지우개다.

Ⅳ. 실무 적용 및 기술사 판단

체크리스트

1. 배수를 지우는 원리를 아는가?
2. 시간/공간 복잡도를 아는가?
3. 소수 테이블을 만들 때 쓰는가?
4. 작은 수부터 반복하는 이유를 아는가?
5. 시험/코딩 문제에서 적용할 수 있는가?

안티패턴

• 수 하나씩 나눠보는 방식만 고집하는 설계
• 메모리 크기를 고려하지 않는 설계
• 소수/합성수 개념을 혼동하는 설계
• 체의 반복 규칙을 잘못 적용하는 설계

기술사 관점에서는 이 알고리즘을 "배수 제거를 통한 소수 생성"으로 설명해야 한다.

• 📢 섹션 요약 비유: 겹치는 것을 지워 소수만 남긴다.

Ⅴ. 기대효과 및 결론

에라토스테네스의 체는 소수 목록을 효율적으로 만든다.

결론적으로 작은 수의 배수를 제거해 소수를 찾는 알고리즘이다.

• 📢 섹션 요약 비유: 소수만 남기는 체다.

관련 개념 맵

Numbers
  ↓
Sieve
  ↓
Primes
  ↓
Number Theory

관련 키워드 및 발전 흐름도

Prime Search
  ↓
Sieve
  ↓
Efficient Filtering

어린이를 위한 3줄 비유 설명

배수를 지워요.
소수만 남아요.
체는 그런 방법이에요.