임의의 자연수 n 이하의 소수를 모두 찾는 간단하고 빠른 방법

  1. 모든 수를 나열한다.
  2. 2를 제외한 2의 배수를 제거한다.
  3. 3을 제외한 3의 배수를 제거한다.
  4. 다음으로 남아있는 가장 작은 소수(5)를 제거한다.

특정 범위의 소수를 판정하는데 효율적이지만, 주어진 수 하나가 소수인지는 소수판정법 사용

Code

func sieveOfEratosthenes(n int) []int {
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }

    for p := 2; p*p <= n; p++ {
        if isPrime[p] {
            for i := p * p; i <= n; i += p {
                isPrime[i] = false
            }
        }
    }

    primes := []int{}
    for p := 2; p <= n; p++ {
        if isPrime[p] {
            primes = append(primes, p)
        }
    }
    
    return primes
}