Add prime searching functions

[?]

Feb 5, 2021, 6:20 PM

7OFUWNAII7HKYHWLPJGIUUJVMQFB4R3JKE3XBKSCVUUAYAWDW6VAC

Dependencies

[2] MCHVA5DY Palindrome initial import

Change contents

file addition: primes (dxwrx-rx-r)

[2.11]
file addition: primes_test.go (-xw-x--x--)

[0.9]

package primes_test

import (
"primes"
"testing"

"github.com/matryer/is"
)

var primeCases = []struct {
input int
expected []int
}{
{0, []int{}},
{1, []int{}},
{2, []int{2}},
{10, []int{2, 3, 5, 7}},
{100, []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}},
}

var sieveCases = []struct {
input int
expected []bool
}{
// every non-prime is true, 0-th and 1-st is false, should be true
{0, []bool{false}},
{1, []bool{false, false}},
{2, []bool{false, false, false}},
{100, []bool{false, false, false, false, true, false, true, false, true, true, true, false, true, false, true, true, true, false, true, false, true, true, true, false, true, true, true, true, true, false, true, false, true, true, true, true, true, false, true, true, true, false, true, false, true, true, true, false, true, true, true, true, true, false, true, true, true, true, true, false, true, false, true, true, true, true, true, false, true, true, true, false, true, false, true, true, true, true, true, false, true, true, true, false, true, true, true, true, true, false, true, true, true, true, true, true, true, false, true, true, true}},
}

func TestPrimes(t *testing.T) {
is := is.New(t)
for _, tc := range primeCases {
is.Equal(tc.expected, primes.Primes(tc.input))
}
}

func TestSieve(t *testing.T) {
is := is.New(t)
for _, tc := range sieveCases {
is.Equal(tc.expected, primes.JustSieve(tc.input))
}
}

func BenchmarkPrimes(b *testing.B) {
for i := 0; i < b.N; i++ {
primes.Primes(1e6)
}
}

func BenchmarkSieve(b *testing.B) {
for i := 0; i < b.N; i++ {
primes.JustSieve(1e6)
}
}
file addition: primes.go (-xw-x--x--)

[0.9]

// Package primes is for calculating primes using sieve of Eratosthenes.
package primes

import (
"fmt"
)

const max = int(10e5)

// Sieve holds the factors for a given number.
type Sieve map[int][]int

var mysieve = make(Sieve, max)

func genSieve(n int) {
for i := 1; i <= n; i++ {
for j := i; j <= n; j += i {
mysieve[j] = append(mysieve[j], i)
}
}
}

// ListPrimes returns the primes below n.
func ListPrimes(n int) ([]int, error) {
if n > max && n < 1 {
return nil, fmt.Errorf("%d is too high or low, max: %d, min: 1", n, max)
}

genSieve(n)

var primes []int
for i := 2; i < n; i++ {
if len(mysieve[i]) == 2 {
primes = append(primes, i)
}
}
return primes, nil
}

func Primes(limit int) []int {
sieve := make([]bool, limit+1)
out := []int{}
for p := 2; p <= limit; p++ {
if !sieve[p] {
out = append(out, p)
for i := p * p; i <= limit; i += p {
sieve[i] = true
}
}
}
return out
}

func JustSieve(limit int) []bool {
sieve := make([]bool, limit+1)
for p := 2; p <= limit; p++ {
if !sieve[p] {
for i := p * p; i <= limit; i += p {
sieve[i] = true
}
}
}
return sieve
}