에라토스테네스의 체에 대해 알아보자
에라토스테네스의 체란?
많은 수 중 소수를 빠르고 정확하게 판별하는 알고리즘이다.
원리
어떤 수의 소수 여부 확인에 있어서는 특정한 숫자의 제곱근까지만 약수 여부를 검증하면 시간 복잡도 O(N^1/2)으로 빠르게 구할 수 있다.
따라서 2부터 n 까지의 소수를 구한다고 가정한다면, 2부터 √n까지 돌면서 배수들을 제거하는 방식이다.
순차적으로 진행하면 다음과 같다.
1package main
2
3import (
4 "fmt"
5 "math"
6)
7
8const n = 1000
9
10func main() {
11 var filter []bool
12 filter = make([]bool, n+1)
13 filter[1] = true
14
15 for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
16 if filter[i] {
17 continue
18 }
19 for j := i * 2; j < n; j += i {
20 filter[j] = true
21 }
22 }
23
24 for i := 1; i < n; i++ {
25 if !filter[i] {
26 fmt.Println(i)
27 }
28 }
29}