{"header":{"message":"primes: add Erastothenes sieve solutions and tests","description":null,"timestamp":"2021-10-20T15:34:12.308291063Z","authors":[{}]},"hash":"7IEM2GFH5X7ZDBWA3LRKU3EU2XRPNGDEQSXXUBLV7T32WA4TI6NQC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["7IEM2GFH5X7ZDBWA3LRKU3EU2XRPNGDEQSXXUBLV7T32WA4TI6NQC","primes: add Erastothenes sieve solutions and tests"],["AA",null],["7OFUWNAII7HKYHWLPJGIUUJVMQFB4R3JKE3XBKSCVUUAYAWDW6VAC","Add prime searching functions"]],"deps":["7OFUWNAII7HKYHWLPJGIUUJVMQFB4R3JKE3XBKSCVUUAYAWDW6VAC"],"known":[]},"hunks":[{"Edit":{"inode":{"change":2,"pos":1695},"path":"snippets/primes/primes.go","line":7,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":1803}],"down_context":[{"change":2,"pos":1803}],"flag":"BLOCK","start":0,"end":21,"inode":{"change":2,"pos":1695}}},"contents":[{"Add":""},{"Add":"const MAX = 105_000"}]}},{"FileAdd":{"meta":{"basename":"erastothenes_test.go","metadata":0},"context":[{"change":2,"pos":9}],"contents":[{"Add":"package primes_test"},{"Add":""},{"Add":"import ("},{"Add":"\t\"primes/erastothenes\""},{"Add":"\t\"testing\""},{"Add":")"},{"Add":""},{"Add":"const benchNum = 10_001"},{"Add":""},{"Add":"func TestUnoptimized(t *testing.T) {"},{"Add":"\tt.Parallel()"},{"Add":"\tfor _, tc := range TestCases {"},{"Add":"\t\tt.Run(tc.description, func(t *testing.T) {"},{"Add":"\t\t\tif tc.p != erastothenes.Nth(\"unoptimized\", tc.n) {"},{"Add":"\t\t\t\tt.FailNow()"},{"Add":"\t\t\t}"},{"Add":"\t\t})"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func TestSkipEven(t *testing.T) {"},{"Add":"\tt.Parallel()"},{"Add":"\tfor _, tc := range TestCases {"},{"Add":"\t\tt.Run(tc.description, func(t *testing.T) {"},{"Add":"\t\t\tif tc.p != erastothenes.Nth(\"skipeven\", tc.n) {"},{"Add":"\t\t\t\tt.FailNow()"},{"Add":"\t\t\t}"},{"Add":"\t\t})"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func TestStartPower(t *testing.T) {"},{"Add":"\tt.Parallel()"},{"Add":"\tfor _, tc := range TestCases {"},{"Add":"\t\tt.Run(tc.description, func(t *testing.T) {"},{"Add":"\t\t\tif tc.p != erastothenes.Nth(\"power\", tc.n) {"},{"Add":"\t\t\t\tt.FailNow()"},{"Add":"\t\t\t}"},{"Add":"\t\t})"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func TestOnlyTilRoot(t *testing.T) {"},{"Add":"\tt.Parallel()"},{"Add":"\tfor _, tc := range TestCases {"},{"Add":"\t\tt.Run(tc.description, func(t *testing.T) {"},{"Add":"\t\t\tif tc.p != erastothenes.Nth(\"root\", tc.n) {"},{"Add":"\t\t\t\tt.FailNow()"},{"Add":"\t\t\t}"},{"Add":"\t\t})"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func TestOptimized(t *testing.T) {"},{"Add":"\tt.Parallel()"},{"Add":"\tfor _, tc := range TestCases {"},{"Add":"\t\tt.Run(tc.description, func(t *testing.T) {"},{"Add":"\t\t\tif tc.p != erastothenes.Nth(\"opt\", tc.n) {"},{"Add":"\t\t\t\tt.FailNow()"},{"Add":"\t\t\t}"},{"Add":"\t\t})"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func BenchmarkUnoptimized(b *testing.B) {"},{"Add":"\tfor i := 0; i < b.N; i++ {"},{"Add":"\t\terastothenes.Nth(\"unoptimized\", benchNum)"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func BenchmarkSkipEven(b *testing.B) {"},{"Add":"\tfor i := 0; i < b.N; i++ {"},{"Add":"\t\terastothenes.Nth(\"skipeven\", benchNum)"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func BenchmarkStartPower(b *testing.B) {"},{"Add":"\tfor i := 0; i < b.N; i++ {"},{"Add":"\t\terastothenes.Nth(\"power\", benchNum)"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func BenchmarkOnlyTilRoot(b *testing.B) {"},{"Add":"\tfor i := 0; i < b.N; i++ {"},{"Add":"\t\terastothenes.Nth(\"root\", benchNum)"},{"Add":"\t}"},{"Add":"}"},{"Add":""},{"Add":"func BenchmarkOptimized(b *testing.B) {"},{"Add":"\tfor i := 0; i < b.N; i++ {"},{"Add":"\t\terastothenes.Nth(\"opt\", benchNum)"},{"Add":"\t}"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"erastothenes","metadata":576},"context":[{"change":2,"pos":9}],"contents":[]}},{"FileAdd":{"meta":{"basename":"erastothenes.go","metadata":0},"context":[{"change":0,"pos":1793}],"contents":[{"Add":"// Package erastothenes implements a sieve of Erastothenes with various optimizations."},{"Add":"package erastothenes"},{"Add":""},{"Add":"import ("},{"Add":"\t\"primes\""},{"Add":")"},{"Add":""},{"Add":"// Unoptimized is the basic method without any optimization or thinking."},{"Add":"func Unoptimized(n int) []bool {"},{"Add":"\tsieve := make([]bool, n+1)"},{"Add":"\tfor i := 2; i <= n; i++ {"},{"Add":"\t\tfor j := 2 * i; j <= n; j += i {"},{"Add":"\t\t\tsieve[j] = true"},{"Add":"\t\t}"},{"Add":"\t}"},{"Add":"\treturn sieve"},{"Add":"}"},{"Add":""},{"Add":"// SkipEven skips even numbers."},{"Add":"func SkipEven(n int) []bool {"},{"Add":"\tsieve := make([]bool, n+1)"},{"Add":"\tfor i := 2; i <= n; i += 2 {"},{"Add":"\t\tfor j := 2 * i; j <= n; j += i {"},{"Add":"\t\t\tsieve[j] = true"},{"Add":"\t\t}"},{"Add":"\t\tif i == 2 {"},{"Add":"\t\t\ti--"},{"Add":"\t\t}"},{"Add":"\t}"},{"Add":"\treturn sieve"},{"Add":"}"},{"Add":""},{"Add":"// StartPower starts with j = i*i."},{"Add":"func StartPower(n int) []bool {"},{"Add":"\tsieve := make([]bool, n+1)"},{"Add":"\tfor i := 2; i <= n; i++ {"},{"Add":"\t\tfor j := i * i; j <= n; j += i {"},{"Add":"\t\t\tsieve[j] = true"},{"Add":"\t\t}"},{"Add":"\t}"},{"Add":"\treturn sieve"},{"Add":"}"},{"Add":""},{"Add":"// OnlyTilRoot stops outer loop at i*i

…

Dependencies

Change contents