에라토스테네스의 체
에라토스테네스의 체 - 나무위키
임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른[2] 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자. 일단 1부터 100까지 숫자를 쭉 쓴다. 1234567891011121314151617181920212223
namu.wiki
100을 예로 들면 2,3,5,7의 배수들을 체에 거르듯 빼주면 소수들만 남는다.
100까지 모든 숫자들을 하나하나 소수인지 판별할 필요 없어서 빠르다.
'TIL' 카테고리의 다른 글
| TIL 042523 (0) | 2023.04.25 |
|---|---|
| TIL 042423 (0) | 2023.04.24 |
| TIL 042023 (0) | 2023.04.20 |
| TIL 041923 (0) | 2023.04.19 |
| TIL 041823 (0) | 2023.04.18 |