Golang : Sieve of Eratosthenes algorithm

Tags :

For this tutorial, we will learn about sieve of Eratosthenes algorithm. Sieve of Eratosthenes is an algorithm for generating all prime numbers less than or equal to a given number N. (up to 10,000,000)

For instance, if an input number is 20 , then all primes less than or equal to 20 would be (2,5,7,11,13,17,19).

Here you go!

package main

import (
"fmt"
)

func displayPrime(num int, prime []bool) {
fmt.Printf("Primes less than %d : ", num)
for i := 2; i <= num; i++ {
if prime[i] == false {
fmt.Printf("%d ", i)
}
}
fmt.Println()
}

func sieve(num int) {

// do not use
// prime := [num+1]bool
// will cause : non-constant array bound num + 1 error

// an array of boolean - the idiomatic way
prime := make([]bool, num+1)

// initialize everything with false first(not crossed)
for i := 0; i < num+1; i++ {
prime[i] = false
}

for i := 2; i*i <= num; i++ {
if prime[i] == false {
for j := i * 2; j <= num; j += i {
prime[j] = true // cross
}
}

}

displayPrime(num, prime)

}

func main() {
sieve(30)
sieve(10)
sieve(60)
}

Output:

Primes less than 30 : 2 3 5 7 11 13 17 19 23 29

Primes less than 10 : 2 3 5 7

Primes less than 60 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59

Reference:

https://en.wikipedia.org/wiki/SieveofEratosthenes

Tags :