야나이 마사카즈의 "더 나은 프로그래밍을 위한 코드골프"라는 책을 읽다가,
'에라스토테네스의 체'라는 내용이 나와서 좀더 자세히 알아보게 되었다.
소수를 구하는 알고리즘인데,
1부터 n까지의 모든 소수를 구한다고 할 때
n까지 다 계산할 필요 없이
sqrt(n)까지만 계산하면 되는 방법이다.
무작정 n까지 다 계산하는 방법보다는 훨씬 나은 방법이다.
즉, 종이에 1부터 n까지 모두 써 놓고,
일단 1을 지운 다음,
2를 소수 리스트에 추가하고 종이에서 2의 배수를 모두 지운다.
다음 숫자들에 대해서도 2에 대한 과정을 반복하되,
이미 지운 숫자는 건너뛰고,
현재의 숫자의 제곱이 n보다 작을 때까지만 반복한다.
현재의 숫자의 제곱이 n보다 커지면,
종이에 남은 숫자를 모두 소수 리스트에 추가하면 된다.
현재의 숫자의 제곱이 n보다 커졌을 때 남은 숫자를
모두 소수 리스트에 추가할 수 있는 이유는 다음과 같다.
현재의 숫자를 i라고 할 때,
i보다 작은 수들의 배수는 이미 목록에서 지워졌고,
i 및 i보다 큰 수의 배수는 최소값이 i * i보다 커야 하는데 i * i가 n보다 크므로,
n이하의 남은 수들은 1과 자신 이외의 약수가 존재하지 않는다.
따라서, 모두 소수 리스트에 추가할 수 있다.
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수(소쑤)를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초
ko.wikipedia.org
관련 블로그 및 기타
[소수 알고리즘] 소수의 특성과 에라토스테네스의 체
[소수 알고리즘] 소수의 특성과 에라토스테네스의 체 소수의 특성 소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수이다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현된..
ledgku.tistory.com
소수 구하기 (Finding Primes) 알고리즘
어떤 자연수 n 이 소수인지 구할때, n 이 작을 경우에는 다음과 같은 방법을 사용한다. 1. Trial Division 소수의 성질을 이용, 어떤 수 n 이 소수인지 판별하기 위해 n 을 2 부터 n-1 까지 하나씩 나누어보아 나..
soyoja.com
지구 둘레 구하는 가장 쉬운 방법 - 이웃집과학자
www.astronomer.rocks
에라토스테네스 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 에라토스테네스(Ερατοσθένης, 기원전 274년 ~ 기원전 196년)는 고대 그리스의 수학자이자 천문학자이다. 헬레니즘 시대 이집트에서 활약했으며, 문헌학 및 지리학을 비롯해 헬레니즘 시대 학문 다방면에 걸쳐 업적을 남겼지만, 특히 수학과 천문학의 분야에서 후세에 남는 큰 업적을 남겼다. 지구의 크기를 처음으로 계산해 냈으며, 또 소수를 걸러내는 에라토스테네스의 체를 고안한 것으로도 알려져 있다. 이런 업적으로 제2
ko.wikipedia.org
'기타' 카테고리의 다른 글
| 영어공부 채널 (0) | 2019.08.04 |
|---|---|
| 티니안섬 (0) | 2019.08.03 |
| 검색엔진에서 GitHub 페이지 검색 가능하게 하기(링크) (0) | 2018.05.10 |
| 티스토리에 소스코드 보기좋게 표시하는 방법(링크) (0) | 2018.04.09 |
| 전세보증보험(전세보증금반환보증) 가입을 위한 필요서류 (0) | 2018.04.04 |