README
¶
Prime
This is a Go library to produce prime numbers using all available cpu cores.
Installation
$ go get github.com/kavehmz/prime
Usage
package main
import (
"fmt"
"github.com/kavehmz/prime"
)
func main() {
p := prime.Primes(1000000)
fmt.Println("Number of primes:", len(p))
}
Algorithm
To find more about different methods to find a range of prime numbers you can look at following pages:
- Sieve of Eratosthenes This is a more memory demanding method but faster by far for larger numbers. Here I have implemented both Segmented and non-Segmented methods. Segmented method had must less memory footprint.
- Trial division Easier to understand and less memory consuming.
Performance
Performance depends on the size of max number. But as an example, it needs about 3ms to produce the first 1,000,000 prime numbers.
$ go test -bench .
PASS
BenchmarkPrimes-4 500 3181972 ns/op
ok github.com/kavehmz/prime 1.618s
| x | no segment | segmented |
|---|---|---|
| 1,000,000 | 0.003s | 0.007s |
| 10,000,000 | 0.035s | 0.044s |
| 100,000,000 | 0.642s | 0.345s |
| 1,000,000,000 | 8.253s | 3.146s |
These calculations are done on a 3.1GHz Dual-core Intel Core i7.
Profiling
If you like to see how profiling in Go works and you have a usage Go installation you can use pprof.
First go and get the package
$ go get github.com/kavehmz/prime
$ cd $GOPATH/src/github.com/kavehmz/prime
$ go build example/main.go
$ ./main -cpuprofile=prime.prof -memprofile=prime.mprof
$ # For inspecting memory usage do
$ go tool pprof main prime.mprof
$ # For inspecting cpu usage do
$ go tool pprof main prime.prof
Entering interactive mode (type "help" for commands)
(pprof) list
To learn how you have use pprof look at the following links:
Why
I used this simple library mainly to learn Go language, Go standards and for solving problems in https://projecteuler.net/
It can also be useful as a relatively fast implementation of prime numbers generator in Go.
Documentation
¶
Overview ¶
Package prime provides functionality to produce prime numbers using all available cpu cores. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes can be an starting point to find more information about how to calculate prime numbers.
The method used in Primes function is Segmented sieve. Segmenting will Reduce memory requirement of process. The space complexity of the algorithm is O(√n).
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Primes ¶
Primes is using Segmented sieve. This method will reduce memory usae of Sieve of Eratosthenes considerably. besides memory allocation for Prime numbers slice, there is only O(sqrt(n)) extra memory required for the operation You can learn more about it in https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
Example ¶
p := Primes(50) fmt.Println(p)
Output: [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47]
func SieveOfEratosthenes ¶
SieveOfEratosthenes returns a slice of all prime numbers equal or lower than max using Sieve Of Eratosthenes. This is without segmenting.
Types ¶
This section is empty.
Source Files
Directories