primes: add ConcurrentSieve

Dependencies

• [2] 7OFUWNAI Add prime searching functions
• [3] LZXA7BOK Make sieve much faster

Change contents

• replacement in snippets/primes/primes_test.go at line 40
  [2.1358]→[2.1358:1389](∅→∅)
  − func TestSieve(t *testing.T) {
  [2.1358]

  [2.1389]
  + func TestJustSieve(t *testing.T) {
• edit in snippets/primes/primes_test.go at line 47
  [2.1497]

  [2.1497]
  + func TestConcSieve(t *testing.T) {

  + is := is.New(t)

  + for _, tc := range sieveCases {

  + is.Equal(tc.expected, primes.ConcurrentSieve(tc.input))

  + }

  + }

  +
• replacement in snippets/primes/primes_test.go at line 60
  [2.1589]→[2.1589:1625](∅→∅)
  − func BenchmarkSieve(b *testing.B) {
  [2.1589]

  [2.1625]
  + func BenchmarkJustSieve(b *testing.B) {
• edit in snippets/primes/primes_test.go at line 63
  [2.1677]

  [2.1677]
  + }

  + }

  +

  + func BenchmarkConcurrentSieve(b *testing.B) {

  + for i := 0; i < b.N; i++ {

  + primes.ConcurrentSieve(1e6)
• edit in snippets/primes/primes.go at line 6
  [2.1801]

  [2.1801]
  + "sync"
• edit in snippets/primes/primes.go at line 69
  [2.2832]
  +

  + func ConcurrentSieve(limit int) []bool {

  + sieve := make([]bool, limit+1)

  + wg := new(sync.WaitGroup)

  + wg.Add(1)

  + go func() {

  + // handle even numbers

  + for i := 2 * 2; i <= limit; i += 2 {

  + sieve[i] = true

  + }

  + wg.Done()

  + }()

  + for p := 3; p*p <= limit; p += 2 {

  + wg.Add(1)

  + go func(p int) {

  + if !sieve[p] {

  + for i := p * p; i <= limit; i += p {

  + sieve[i] = true

  + }

  + }

  + wg.Done()

  + }(p)

  + }

  + wg.Wait()

  + return sieve

  + }