package main
import "fmt"
// Send the sequence 2, 3, 4, ... to channel 'ch'
func Generate(ch chan<- int) {
for i := 2; ; i++ {
ch <- i // Send 'i' to channel 'ch'
}
}
// Copy the values from channel 'in' to channel 'out',
// removing the multiples of 'prime'.
// 'in' is assumed to send increasing numbers
func Filter(in <-chan int, out chan<- int, prime int) {
m := prime * prime // start from square of prime
for {
i := <- in // Receive value from 'in'
for i > m {
m = m + prime // next multiple of prime
}
if i < m {
out <- i // Send 'i' to 'out'
}
}
}
// The prime sieve: Postponed-creation Daisy-chain Filter processes
func Sieve(out chan<- int) {
ch := make(chan int) // Create a new channel
go Generate(ch) // Launch Generate goroutine
prime := <- ch
out <- prime
// new
prime = <- ch // shallower recursion!
out <- prime
base_primes := make(chan int) // separate primes supply
go Sieve(base_primes)
bp := <- base_primes // 2
bq := bp*bp // 4
for {
prime = <- ch
if prime == bq { // square of a base prime
ch1 := make(chan int)
go Filter(ch, ch1, bp)
ch = ch1
bp = <- base_primes // 3
bq = bp*bp // 9
} else {
out <- prime
}
}
}
func main() {
ch := make(chan int) // Create a new channel
go Sieve(ch) // Launch Sieve goroutine
lim := 25000 // now it works
for i := 0; i < lim; i++ {
prime := <- ch
if i >= (lim-5) {
fmt.Printf("%4d ", prime)
//if (i+1)%20==0 {
// fmt.Println("")
//}
}
}
}
/*
25000: was: Runtime error time: 4.57 memory: 791552 signal:25
now: shallower recursion: 4.22s
20000: time: 4.35 memory: 791552 signal:0 ---- n^1.2 ----
224699 224711 224717 224729 224737
10000: time: 1.91 memory: 790528 signal:0 ---- n^1.2 ----
104707 104711 104717 104723 104729
1000: time: 0.12 memory: 790016 signal:0
7879 7883 7901 7907 7919
*/