8

[Golang] Sieve of Eratosthenes

 3 years ago
source link: http://siongui.github.io/2017/04/17/go-sieve-of-eratosthenes/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[Golang] Sieve of Eratosthenes

April 17, 2017

Go implementation of Sieve of Eratosthenes. See from GeeksforGeeks [1]. The Go code is ported from the C/C++ code of GeeksforGeeks.

Run Code on Go Playground

package main

import (
      "fmt"
)

func SieveOfEratosthenes(n int) []int {
      // Create a boolean array "prime[0..n]" and initialize
      // all entries it as true. A value in prime[i] will
      // finally be false if i is Not a prime, else true.
      integers := make([]bool, n+1)
      for i := 2; i < n+1; i++ {
              integers[i] = true
      }

      for p := 2; p*p <= n; p++ {
              // If integers[p] is not changed, then it is a prime
              if integers[p] == true {
                      // Update all multiples of p
                      for i := p * 2; i <= n; i += p {
                              integers[i] = false
                      }
              }
      }

      // return all prime numbers <= n
      var primes []int
      for p := 2; p <= n; p++ {
              if integers[p] == true {
                      primes = append(primes, p)
              }
      }

      return primes
}

func main() {
      fmt.Println(SieveOfEratosthenes(20))
      fmt.Println(SieveOfEratosthenes(30))
      fmt.Println(SieveOfEratosthenes(40))
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK