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.
