fork download
copy 
  1. package main
  2. import "fmt"
  3.  
  4. // Send the sequence 2, 3, 4, ... to channel 'ch'
  5. func Generate(ch chan<- int) {
  6. 	for i := 2; ; i++ {
  7. 		ch <- i    // Send 'i' to channel 'ch'
  8. 	}
  9. }
  10.  
  11. // Copy the values from channel 'in' to channel 'out',
  12. //   removing the multiples of 'prime'.
  13. // 'in' is assumed to send increasing numbers
  14. func Filter(in <-chan int, out chan<- int, prime int) {
  15. 	m := prime * prime        // start from square of prime
  16. 	for {
  17. 		i := <- in        // Receive value from 'in'
  18. 		for i > m {
  19. 			m = m + prime     // next multiple of prime
  20. 		}
  21. 		if i < m {
  22. 			out <- i  // Send 'i' to 'out'
  23. 		}
  24. 	}
  25. }
  26.  
  27. // The prime sieve: Postponed-creation Daisy-chain Filter processes
  28. func Sieve(out chan<- int) {
  29. 	ch := make(chan int)    // Create a new channel
  30. 	go Generate(ch)        // Launch Generate goroutine
  31. 	prime := <- ch
  32. 	out <- prime
  33. 	 // new
  34. 	prime = <- ch      // shallower recursion!
  35. 	out <- prime
  36.  
  37. 	base_primes := make(chan int)  // separate primes supply
  38. 	go Sieve(base_primes)
  39. 	bp := <- base_primes    // 2
  40. 	bq := bp*bp             // 4
  41.  
  42. 	for  {
  43. 		prime = <- ch
  44. 		if prime == bq {       // square of a base prime
  45. 			ch1 := make(chan int)
  46. 			go Filter(ch, ch1, bp)
  47. 			ch = ch1
  48. 			bp = <- base_primes    // 3
  49. 			bq = bp*bp             // 9
  50. 		} else {
  51. 			out <- prime
  52. 		}
  53. 	}
  54. }
  55.  
  56. func main() {
  57. 	ch := make(chan int)  // Create a new channel
  58. 	go Sieve(ch)         // Launch Sieve goroutine
  59. 	lim := 25000               // now it works
  60. 	for i := 0; i < lim; i++ {
  61. 		prime := <- ch
  62. 		if i >= (lim-5) {
  63. 		    fmt.Printf("%4d ", prime)
  64. 		    //if (i+1)%20==0 {
  65. 			//	fmt.Println("")
  66. 		    //}
  67. 		}
  68. 	}
  69. }
  70. /*
  71. 25000:  was: Runtime error	time: 4.57 memory: 791552 signal:25
  72.  now: shallower recursion: 4.22s
  73.  
  74. 20000:	time: 4.35 memory: 791552 signal:0    ---- n^1.2 ----
  75. 224699 224711 224717 224729 224737 
  76.  
  77. 10000:	time: 1.91 memory: 790528 signal:0    ---- n^1.2 ----
  78. 104707 104711 104717 104723 104729 
  79.  
  80. 1000:	time: 0.12 memory: 790016 signal:0
  81. 7879 7883 7901 7907 7919 
  82. */
Success #stdin #stdout 4.22s 791552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
287087 287093 287099 287107 287117
https://ideone.com/I0AXf5
for http://r...content-available-to-author-only...e.org/wiki/Sieve_of_Eratosthenes#Postponed_Concurrent_Daisy-chain_sieve
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!