primes

func Coprime ¶

func Coprime(a, b int) bool

Coprime is a coprimality test: it returns true if the only positive integer that divides evenly both a and b is 1. This function implements the division-based version of the Euclidean algorithm. See https://en.wikipedia.org/wiki/Coprime_integers and https://en.wikipedia.org/wiki/Euclidean_algorithm for details.

package main

import (
	"fmt"

	"github.com/fxtlabs/primes"
)

func main() {
	// Check which combinations are coprime
	ns := []int{2, 3, 4, 5, 6}
	for i, a := range ns {
		for _, b := range ns[i+1:] {
			if primes.Coprime(a, b) {
				fmt.Printf("%d and %d are coprime\n", a, b)
			}
		}
	}

}

Output:

2 and 3 are coprime
2 and 5 are coprime
3 and 4 are coprime
3 and 5 are coprime
4 and 5 are coprime
5 and 6 are coprime

func IsPrime ¶

func IsPrime(n int) bool

IsPrime is a primality test: it returns true if n is prime. It uses trial division to check whether n can be divided exactly by any number that is less than n. The algorithm can be very slow on large n despite a number of optimizations:

* If n is relatively small, it is compared against a cached table of primes.

* Only numbers up to sqrt(n) are used to check for primality.

* n is first checked for divisibility by the primes in the cache and only if the test is inconclusive, n is checked against more numbers.

* Only numbers of the form 6*k+|-1 that are greater than the last prime in the cache are checked after that.

See https://en.wikipedia.org/wiki/Primality_test and https://en.wikipedia.org/wiki/Trial_division for details.

package main

import (
	"fmt"
	"math"

	"github.com/fxtlabs/primes"
)

func main() {
	// Check which numbers are prime
	ns := []int{2, 23, 49, 73, 98765, 1000003, 10007 * 10009, math.MaxInt32}
	for _, n := range ns {
		if primes.IsPrime(n) {
			fmt.Printf("%d is prime\n", n)
		} else {
			fmt.Printf("%d is composite\n", n)
		}
	}

}

Output:

2 is prime
23 is prime
49 is composite
73 is prime
98765 is composite
1000003 is prime
100160063 is composite
2147483647 is prime

func Pi ¶

func Pi(n int) (pi int, ok bool)

Pi returns the number of primes less than or equal to n. If ok is true, the result is correct; otherwise it is an estimate computed as n/(log(n)-1) with an error generally below 1% (see tests). This estimate is based on the prime number theorem which states that the number of primes not exceeding n is asymptotic to n/log(n). Better approximations are known, but they are more complex. See https://primes.utm.edu/howmany.html#1, https://en.wikipedia.org/wiki/Prime_number_theorem, and https://en.wikipedia.org/wiki/Prime-counting_function for details.

package main

import (
	"fmt"

	"github.com/fxtlabs/primes"
)

func main() {
	// Check how many prime numbers are less than or equal to n
	ns := []int{6, 11, 23, 12345}
	for _, n := range ns {
		pi, ok := primes.Pi(n)
		if ok {
			fmt.Printf("There are %d primes in [0,%d]\n", pi, n)
		} else {
			fmt.Printf("There are approximately %d primes in [0,%d]\n", pi, n)
		}
	}

}

Output:

There are 3 primes in [0,6]
There are 5 primes in [0,11]
There are 9 primes in [0,23]
There are approximately 1465 primes in [0,12345]

func Sieve ¶

func Sieve(n int) []int

Sieve returns a list of the prime numbers less than or equal to n. If n is less than 2, it returns an empty list. The function uses the sieve of Eratosthenes algorithm (see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) with the following optimizations:

* The initial list of candidate primes includes odd numbers only.

* Given a prime p, only multiples of p greater than or equal to p*p need to be marked off since smaller multiples of p have already been marked off by then.

* The above also implies that the algorithm can terminate as soon as it finds a prime p such that p*p is greater than n.

Sieve takes O(n) memory and runs in O(n log log n) time.

package main

import (
	"fmt"

	"github.com/fxtlabs/primes"
)

func main() {
	// Generate the prime numbers less than or equal to 20
	ps := primes.Sieve(20)
	fmt.Println(ps)

}

Output:

[2 3 5 7 11 13 17 19]