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:
See also : Golang : How to determine a prime number?
By Adam Ng
IF you gain some knowledge or the information here solved your programming problem. Please consider donating to the less fortunate or some charities that you like. Apart from donation, planting trees, volunteering or reducing your carbon footprint will be great too.
Advertisement
Tutorials
+19.2k PHP : Convert(cast) int to double/float
+5.6k Golang : Humanize and Titleize functions
+31.2k Golang : Regular Expression for alphanumeric and underscore
+10.7k Golang : Pagination with go-paginator configuration example
+13.5k Golang : Find commonalities in two slices or arrays example
+12.8k Golang : convert(cast) string to float value
+13.9k Golang : Force download file example
+21.4k Golang : simulate tail -f or read last line from log file example
+24.6k Mac/Linux and Golang : Fix bind: address already in use error
+6.8k Golang : Error reading timestamp with GORM or SQL driver
+22.8k Golang : How to print rune, unicode, utf-8 and non-ASCII CJK(Chinese/Japanese/Korean) characters?
+10.3k Golang : GTK Input dialog box examples