const MAX = 105_000

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)
	}
}

// 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
} 

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,
	},
}