pijul nest
guest › [sign in] [explore]

remove old primes and tests

voroskoi
Oct 20, 2021, 4:00 PM
26LVTPUV7J6VMMUAXCABXG5Z5BY76ETAYRRJA6SSS7Q27SBQFX7QC

Dependencies

  • [2] LZXA7BOK Make sieve much faster
  • [3] BCVIGM7N primes: add ConcurrentSieve
  • [4] MQF53D2U pijul WTF
  • [5] 7IEM2GFH primes: add Erastothenes sieve solutions and tests
  • [6] VTLT4FAD Remove Primes function, move factor calculations to separate directory
  • [7] 7OFUWNAI Add prime searching functions

Change contents

  • file deletion: primes_test.go (-xw-x--x--)primes_test.go (----------)
    [6.9]→[6.10:26](∅→∅),[6.26]→[6.27:27](∅→∅),[6.9]→[4.246:271](∅→∅),[4.271]→[6.27:27](∅→∅)
    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}},
    }
    is := is.New(t)
    for _, tc := range sieveCases {
    is.Equal(tc.expected, primes.JustSieve(tc.input))
    }
    }
    for i := 0; i < b.N; i++ {
    primes.JustSieve(1e6)
    }
    }
    }
    }
    func BenchmarkConcurrentSieve(b *testing.B) {
    for i := 0; i < b.N; i++ {
    primes.ConcurrentSieve(1e6)
    func BenchmarkJustSieve(b *testing.B) {
    func TestConcSieve(t *testing.T) {
    is := is.New(t)
    for _, tc := range sieveCases {
    is.Equal(tc.expected, primes.ConcurrentSieve(tc.input))
    }
    }
    func TestJustSieve(t *testing.T) {
    {10, []bool{false, false, false, false, true, false, true, false, true, true, true}},
  • edit in snippets/primes/primes.go at line 3
    [6.1784]→[6.1784:1794](∅→∅),[6.1801]→[3.338:346](∅→∅),[3.346]→[6.1801:1803](∅→∅),[6.1801]→[6.1801:1803](∅→∅),[6.1803]→[5.0:21](∅→∅),[5.21]→[6.1803:1804](∅→∅),[6.1803]→[6.1803:1804](∅→∅),[6.2629]→[6.2629:2696](∅→∅),[6.2696]→[2.88:124](∅→∅),[2.124]→[6.2727:2809](∅→∅),[6.2727]→[6.2727:2809](∅→∅),[6.2809]→[2.125:153](∅→∅),[2.153]→[6.2809:2832](∅→∅),[6.2809]→[6.2809:2832](∅→∅)
    import (
    "sync"
    )
    const MAX = 105_000
    func JustSieve(limit int) []bool {
    sieve := make([]bool, limit+1)
    for p := 2; p*p <= limit; p += 2 {
    if !sieve[p] {
    for i := p * p; i <= limit; i += p {
    sieve[i] = true
    }
    if p == 2 {
    p--
    }
    }
    }
    return sieve
    }
  • replacement in snippets/primes/primes.go at line 4
    [3.348]→[3.348:784](∅→∅)
    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
    }
    [3.348]
    const MAX = 105_000