piątek, 4 listopada 2022

[Let`s go with golang] Eratosthenes Sieve

I start weekend, so I write simple algorithm :)
Some time ago I searched Archimedes sieve, but I found Eratosthenes Sieve, 
 Today I implement it, because I can.

func EratosthenesSieve(n int) []int {
    numbersNoFirst := make([]bool, n)
    result := make([]int, 0)
    if n < 1 {
        return result
    }
    numbersNoFirst[0] = true
    for i := 2; i <= n; i++ {
        if numbersNoFirst[i-1] {
            continue
        }
        j := 2
        for i*j <= n {
            numbersNoFirst[(i*j)-1] = true
            j++
        }
    }

    for i := 0; i < n; i++ {
        if !numbersNoFirst[i] {
            result = append(result, i+1)
        }
    }
    return result[:]
}

Brak komentarzy:

Prześlij komentarz