에라토스테네스의 체 소개 - 가장 오래된 소수 체
에라토스테네스의 체는 나눗셈을 한 번도 하지 않고 한계까지의 모든 소수를 찾습니다. 세기만 하면 됩니다: 2 다음에는 두 번째 수마다, 3 다음에는 세 번째 수마다 지우고, 이렇게 계속합니다. 남은 것이 소수입니다. 이천 년이 넘게 지난 지금도 소수를 나열하는 가장 빠른 방법 중 하나입니다.
키레네의 에라토스테네스
에라토스테네스는 대략 기원전 276년부터 194년까지 살았으며 알렉산드리아 대도서관의 관장이었습니다. 두 도시의 그림자 길이로 지구의 크기를 잰 것으로 가장 유명합니다. 체에 그의 이름이 붙은 것은 게라사의 니코마코스가 서기 100년경에 쓴 『산술 입문』에서 이를 그의 방법으로 소개했기 때문입니다.
체의 원리
2부터 N까지 수를 씁니다. 첫 번째 수 2는 소수입니다: 4, 6, 8과 2의 다른 모든 배수를 지웁니다. 남아 있는 다음 수 3은 소수입니다: 9, 12, 15 등을 지웁니다. 5, 7과 그다음 남은 수로 계속합니다. 한 번도 지워지지 않은 수는 더 작은 약수가 없으므로 소수입니다.
제곱근에서 멈추기
N까지의 모든 합성수는 N의 제곱근보다 크지 않은 소인수를 가집니다. 따라서 p²가 N보다 커지면 더 지울 것이 없습니다. 100까지의 소수에는 2, 3, 5, 7만 있으면 되고, 1000까지는 31까지의 소수만 있으면 됩니다.
얼마나 빠른가요?
체는 약 N log log N 단계가 걸리며, 이는 N 자체보다 조금만 더 빠르게 늘어납니다. 컴퓨터는 지금도 흔히 구간 체로 나누어 수십억까지의 소수를 나열하는 데 이것을 씁니다. 큰 수 하나가 소수인지 확인할 때는 다른 방법이 더 빠릅니다.
자주 묻는 질문
에라토스테네스의 체는 누가 발명했나요?
기원전 3세기 그리스 학자인 키레네의 에라토스테네스의 이름을 땄습니다. 남아 있는 가장 오래된 기록은 서기 100년경 게라사의 니코마코스가 남겼습니다.
왜 체는 p²부터 지우기 시작하나요?
p의 더 작은 배수는 모두 더 작은 소인수를 가지므로 더 작은 소수가 이미 지웠습니다.
1000 미만의 소수는 몇 개인가요?
1000 미만의 소수는 168개입니다. 가장 큰 것은 997입니다.
관련 도구
에라토스테네스의 체
에라토스테네스의 체가 100, 200, 500 또는 1000까지의 소수를 찾는 과정을 지켜보세요. 각 소수가 자신의 색으로 배수를 한 단계씩 지웁니다.
울람 나선
브라우저에서 울람 나선을 그리세요. 소수를 표시하고, 각 대각선의 이차식을 읽고, 오일러의 끊기지 않는 소수 40개 행렬을 열어 보세요.
울람 나선
스타니스와프 울람의 1963년 나선이 정수를 정사각 격자에 어떻게 배치하는지, 왜 소수가 이차식 대각선에 모이는지, 나선을 41에서 시작할 때 오일러의 소수 40개가 어디에 놓이는지 알아봅니다.
콜라츠 추측
브라우저에서 콜라츠 3n+1 문제를 탐험하세요. 우박수열을 따라가고, 기하학적 콜라츠 나무를 키우고, 연속 콜라츠 프랙털을 확대해 보세요.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
에라토스테네스의 체 사용해 보기