에라토스테네스의 체
거의 선형 시간에 N까지의 모든 소수를 나열합니다
에라토스테네스의 체은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
소수를 한꺼번에 찾기
때로는 하나의 수만 확인하는 것이 아니라 N 이하의 모든 소수가 필요합니다. 에라토스테네스의 체를 사용하면 한 번의 스윕으로 모두 찾을 수 있습니다. 🧹
핵심 아이디어
먼저 모든 수를 소수라고 가정합니다. 그런 다음 발견한 각 소수의 배수를 지워 나가면 진짜 소수만 남습니다.
플래그 설정하기
i번째 인덱스가 i가 소수인지 표시하는 불리언 목록을 만듭니다. 이 배열이 체가 표시를 그려 나가는 바탕입니다.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False후보 훑기
i를 증가시키며 살펴봅니다. 아직 참으로 표시된 수에 처음 도달했다면, 그 수는 더 작은 인수를 갖지 않는 새로운 소수임이 분명합니다.
배수 지우기
각 소수 i에 대해 2i, 3i, 4i 등을 소수가 아닌 것으로 표시합니다. 이러한 배수에는 분명히 i가 약수로 들어 있습니다.
for j in range(i * i, n + 1, i):
is_prime[j] = Falsei의 제곱에서 시작하기
2i가 아니라 i*i에서 지우기를 시작합니다. 더 작은 배수는 모두 이전 소수가 이미 제거했으므로 건너뛰어도 됩니다.
제곱근에서 멈추기
i*i가 N 이하인 동안만 체를 수행하면 됩니다. 제곱근을 지나면 남아 있는 참 플래그는 이미 모두 소수입니다.
전체 체
바깥쪽 순회와 안쪽 지우기를 합칩니다. 반복문이 끝난 뒤에도 참으로 표시된 모든 인덱스는 확인된 소수입니다.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False소수 모으기
리스트 컴프리헨션으로 완성된 플래그를 목록에 옮겨 담습니다. 이제 N 이하의 모든 소수를 빠른 질의에 사용할 수 있습니다.
primes = [i for i, p in enumerate(is_prime) if p]빠른 이유
체는 거의 선형인 O(n log log n) 시간에 실행됩니다. 그래서 하나의 수를 반복해서 테스트하는 방법보다 훨씬 뛰어납니다.
메모리 주의하기
플래그 배열은 N에 비례하는 메모리를 사용합니다. 한도가 매우 크다면 할당하기 전에 공간 예산을 확인하십시오.
빠른 확인
안쪽 반복문에서 사용하는 작은 최적화를 떠올려 보십시오.
복습
이제 체를 만들어 N 이하의 모든 소수를 거의 선형 시간에 나열할 수 있습니다. 각 소수는 i*i에서 시작하고 제곱근에서 멈춥니다. ✅
AI 튜터와 함께 Python을(를) 배우세요 — 무료
브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.
- 코스
- 30
- 레슨
- 120
자주 묻는 질문
“에라토스테네스의 체” 강의는 무료인가요?
네 — “에라토스테네스의 체” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“에라토스테네스의 체”에서 뭘 배우나요?
거의 선형 시간에 N까지의 모든 소수를 나열합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“에라토스테네스의 체” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.