primes: add Erastothenes sieve solutions and tests

voroskoi

Oct 20, 2021, 3:34 PM

7IEM2GFH5X7ZDBWA3LRKU3EU2XRPNGDEQSXXUBLV7T32WA4TI6NQC

Dependencies

[2] 7OFUWNAI Add prime searching functions

Change contents

edit in snippets/primes/primes.go at line 7

[2.1803]

[2.1803]

const MAX = 105_000
file addition: erastothenes_test.go (----------)

[2.9]

package primes_test

import (
"primes/erastothenes"
"testing"
)

const benchNum = 10_001

func TestUnoptimized(t *testing.T) {
t.Parallel()
for _, tc := range TestCases {
t.Run(tc.description, func(t *testing.T) {
if tc.p != erastothenes.Nth("unoptimized", tc.n) {
t.FailNow()
}
})
}
}

func TestSkipEven(t *testing.T) {
t.Parallel()
for _, tc := range TestCases {
t.Run(tc.description, func(t *testing.T) {
if tc.p != erastothenes.Nth("skipeven", tc.n) {
t.FailNow()
}
})
}
}

func TestStartPower(t *testing.T) {
t.Parallel()
for _, tc := range TestCases {
t.Run(tc.description, func(t *testing.T) {
if tc.p != erastothenes.Nth("power", tc.n) {
t.FailNow()
}
})
}
}

func TestOnlyTilRoot(t *testing.T) {
t.Parallel()
for _, tc := range TestCases {
t.Run(tc.description, func(t *testing.T) {
if tc.p != erastothenes.Nth("root", tc.n) {
t.FailNow()
}
})
}
}

func TestOptimized(t *testing.T) {
t.Parallel()
for _, tc := range TestCases {
t.Run(tc.description, func(t *testing.T) {
if tc.p != erastothenes.Nth("opt", tc.n) {
t.FailNow()
}
})
}
}

func BenchmarkUnoptimized(b *testing.B) {
for i := 0; i < b.N; i++ {
erastothenes.Nth("unoptimized", benchNum)
}
}

func BenchmarkSkipEven(b *testing.B) {
for i := 0; i < b.N; i++ {
erastothenes.Nth("skipeven", benchNum)
}
}

func BenchmarkStartPower(b *testing.B) {
for i := 0; i < b.N; i++ {
erastothenes.Nth("power", benchNum)
}
}

func BenchmarkOnlyTilRoot(b *testing.B) {
for i := 0; i < b.N; i++ {
erastothenes.Nth("root", benchNum)
}
}

func BenchmarkOptimized(b *testing.B) {
for i := 0; i < b.N; i++ {
erastothenes.Nth("opt", benchNum)
}
}
file addition: erastothenes (d--r------)

[2.9]
file addition: erastothenes.go (----------)

[0.1793]

// Package erastothenes implements a sieve of Erastothenes with various optimizations.
package erastothenes

import (
"primes"
)

// Unoptimized is the basic method without any optimization or thinking.
func Unoptimized(n int) []bool {
sieve := make([]bool, n+1)
for i := 2; i <= n; i++ {
for j := 2 * i; j <= n; j += i {
sieve[j] = true
}
}
return sieve
}

// SkipEven skips even numbers.
func SkipEven(n int) []bool {
sieve := make([]bool, n+1)
for i := 2; i <= n; i += 2 {
for j := 2 * i; j <= n; j += i {
sieve[j] = true
}
if i == 2 {
i--
}
}
return sieve
}

// StartPower starts with j = i*i.
func StartPower(n int) []bool {
sieve := make([]bool, n+1)
for i := 2; i <= n; i++ {
for j := i * i; j <= n; j += i {
sieve[j] = true
}
}
return sieve
}

// OnlyTilRoot stops outer loop at i*i<n.
func OnlyTilRoot(n int) []bool {
sieve := make([]bool, n+1)
for i := 2; i*i <= n; i++ {
for j := 2 * i; j <= n; j += i {
sieve[j] = true
}
}
return sieve
}

// Optimized has all the optimizations above.
func Optimized(n int) []bool {
sieve := make([]bool, n+1)
for i := 2; i*i <= n; i += 2 {
for j := i * i; j <= n; j += i {
sieve[j] = true
}
if i == 2 {
i--
}
}
return sieve
}

func Nth(sieve string, limit int) int {
if limit < 1 {
return 0
}
var s []bool
switch sieve {
case "unoptimized":
s = Unoptimized(primes.MAX)
case "skipeven":
s = SkipEven(primes.MAX)
case "power":
s = StartPower(primes.MAX)
case "root":
s = OnlyTilRoot(primes.MAX)
case "opt":
s = Optimized(primes.MAX)
}

i := 2
for count := 0; count < limit; i++ {
if !s[i] {
count++
}
}
return i - 1
}
file addition: cases_test.go (----------)

[2.9]

package primes_test

var TestCases = []struct {
description string
n int
p int
ok bool
}{
{
"first prime",
1,
2,
true,
},
{
"second prime",
2,
3,
true,
},
{
"sixth prime",
6,
13,
true,
},
{
"big prime",
10001,
104743,
true,
},
{
"there is no zeroth prime",
0,
0,
false,
},
}