Golang : Sieve of Eratosthenes algorithm

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