fork(1) download
copy 
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. func main() {
  6.   ch := make(chan int)
  7.   go Sieve( ch) ;
  8.   n := 20000               // was: 7000 now: 10k: OK: 0.42s 20k:1.16s n^1.47
  9.   for i := 0; i < n; i++ {
  10.     prime := <-ch
  11.     if i > (n-10) {
  12.     	fmt.Printf("%v ", prime)
  13.     	}
  14.   }
  15. }
  16.  
  17. func OddsFrom(from int, ch chan<- int) {
  18.     for i := from; ; i+=2 {
  19.         ch <- i
  20.     }
  21. }
  22.  
  23. func Filter(in <-chan int, out chan<- int, prime int) {
  24.     for {
  25.         i := <-in
  26.         if i%prime != 0 {
  27.             out <- i
  28.         }
  29.     }
  30. }
  31.                        // postponed sieve by trial division - by Will Ness
  32. func Sieve(out chan<- int) {     // 2k: 0.065s !!!   4k: 0.175s  n^1.43
  33.   out <- 2                       // 7k: 0.357s  n^1.27 (1.36) !!
  34.   out <- 3                       // 8k: out-of-memory (33442 goroutines ??)
  35.    // new
  36.   out <- 5    // shallower recursion! good? YES!! 0.26s vs 0.85s for 7k!
  37.   q := 9
  38.   ps := make(chan int)
  39.   go Sieve(ps)                   // separate primes
  40.   p := <-ps                      // p=2, ps@3
  41.   p = <-ps                       // p=3, ps@5
  42.   nums := make(chan int)
  43.   go OddsFrom(7,nums)     // was: 5
  44.   for {
  45.     n := <-nums
  46.     if n < q {
  47.     	out <- n                 // n is prime
  48.     } else {
  49.         ch1 := make(chan int)
  50.         go Filter(nums, ch1, p)  // p=3
  51.         nums = ch1
  52.     	p = <-ps                 // 5
  53.     	q = p*p                  // 25 !
  54.     }
  55.   }
  56. }
  57. /*
  58. func Primes(out chan<- int) {
  59. 	out <- 2
  60.     out <- 3
  61. 	go Sieve(out)
  62. }
  63.  
  64. func Wheel23(from int, by int, ch chan<- int) {
  65.     for i := from; ; i+=6 {
  66.         ch <- i
  67.         ch <- (i+by)  // 2 or 4
  68.     }
  69. }
  70. func NumsFromBy(from int, by int, ch chan<- int) {
  71.     for i := from; ; i+=by {
  72.         ch <- i
  73.     }
  74. }
  75.  
  76. func Sieve(out chan<- int) {     // 2k: 0.1s  4k:0.24s  n^1.26
  77.   out <- 5                       // 7k: out-of-memory WTF
  78.   q := 25
  79.   ps := make(chan int)
  80.   go Sieve(ps)                   // separate primes supply
  81.   p := <-ps                      // p=5, ps@7
  82.   nums := make(chan int)
  83.   go Wheel23(7,4,nums)
  84.   for {
  85.     n := <-nums
  86.     if n < q {
  87.     	out <- n                 // n is prime
  88.     } else {
  89.         ch1 := make(chan int)
  90.         go Filter(nums, ch1, p)  // p=5
  91.         nums = ch1
  92.     	p = <-ps                 // 7
  93.     	q = p*p                  // 49 !
  94.     }
  95.   }
  96. }
  97.  
  98. func Sieve(out chan<- int) {
  99.   ch := make(chan int)
  100.   go NumsFromBy(2,1,ch)
  101.   for i := 0; ; i++ {
  102.     prime := <-ch
  103.     out <- prime
  104.     ch1 := make(chan int)
  105.     go Filter(ch, ch1, prime)
  106.     ch = ch1
  107.   }                            // 1k: 0.27s 2k:1.32s n^2.29 !
  108. }
  109.  
  110. func Sieve(out chan<- int) {   // 1k: 0.3s 2k:1.47s n^2.29 !!
  111.   ch := make(chan int)
  112.   out <- 2
  113.   go NumsFromBy(3,2,ch)
  114.   for i := 0; ; i++ {
  115.     prime := <-ch
  116.     out <- prime
  117.     ch1 := make(chan int)
  118.     go Filter(ch, ch1, prime)   // no postponement! too hasty!
  119.     ch = ch1
  120.   }
  121. }
  122.  
  123. func Sieve(out chan<- int) {     // 1.6k: out-of-memory !!???
  124.   out <- 2                       // 1k: 0.16s  1.2k:0.20s n^1.22
  125.   q := 4
  126.   ps := make(chan int)
  127.   go Sieve(ps)                   // ok, so out-of-memory is NOT
  128.   p := <-ps                      // not amount of channels, but of
  129.   nums := make(chan int)         // overall operations??!?
  130.   go NumsFromBy(3,1,nums)
  131.   for {
  132.     n := <-nums
  133.     if n < q {
  134.     	out <- n                 // n is prime
  135.     } else {
  136.         ch1 := make(chan int)
  137.         go Filter(nums, ch1, p)
  138.         nums = ch1
  139.     	p = <-ps
  140.     	q = p*p
  141.     }
  142.   }
  143. }
  144. */
Success #stdin #stdout 1.16s 789504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
224633 224669 224677 224683 224699 224711 224717 224729 224737
https://ideone.com/RPwHJe
postponed TD-sieve in Go
language:
Go (go 1.12.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!