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' assumed to send increasing numbers
func Filter(in <-chan int, out chan<- int, prime int) {
m := prime + prime
for {
i := <- in // Receive value from 'in'
for i > m {
m = m + prime
}
if i < m {
out <- i // Send 'i' to 'out'
}
}
}
// The prime sieve: Daisy-chain Filter processes
func Sieve(out chan<- int) {
ch := make(chan int) // Create a new channel
go Generate(ch) // Launch Generate goroutine
for {
prime := <-ch
out <- prime
ch1 := make(chan int)
go Filter(ch, ch1, prime)
ch = ch1
}
}
func main() {
ch := make(chan int) // Create a new channel
go Sieve(ch) // Launch Sieve goroutine
m := 3000
for i := 0; i < m; i++ {
prime := <-ch
if i >= (m-5) {
fmt.Printf("%4d ", prime)
//if (i+1)%10==0 {
// fmt.Println("")
//}
}
}
}
/*
3000: time: 4.02 memory: 789504 signal:0 ---- n^2.1 ----
27409 27427 27431 27437 27449
2000: time: 1.75 memory: 789504 signal:0 ---- n^2.1 ----
17359 17377 17383 17387 17389
1000: time: 0.39 memory: 789504 signal:0
7879 7883 7901 7907 7919
*/
cGFja2FnZSBtYWluCmltcG9ydCAiZm10IgoKLy8gU2VuZCB0aGUgc2VxdWVuY2UgMiwgMywgNCwgLi4uIHRvIGNoYW5uZWwgJ2NoJwpmdW5jIEdlbmVyYXRlKGNoIGNoYW48LSBpbnQpIHsKCWZvciBpIDo9IDI7IDsgaSsrIHsKCQljaCA8LSBpICAgIC8vIFNlbmQgJ2knIHRvIGNoYW5uZWwgJ2NoJwoJfQp9CgovLyBDb3B5IHRoZSB2YWx1ZXMgZnJvbSBjaGFubmVsICdpbicgdG8gY2hhbm5lbCAnb3V0JywKLy8gcmVtb3ZpbmcgdGhlIG11bHRpcGxlcyBvZiAncHJpbWUnLgovLyAnaW4nIGFzc3VtZWQgdG8gc2VuZCBpbmNyZWFzaW5nIG51bWJlcnMKZnVuYyBGaWx0ZXIoaW4gPC1jaGFuIGludCwgb3V0IGNoYW48LSBpbnQsIHByaW1lIGludCkgewoJbSA6PSBwcmltZSArIHByaW1lCglmb3IgewoJCWkgOj0gPC0gaW4gICAgLy8gUmVjZWl2ZSB2YWx1ZSBmcm9tICdpbicKCQlmb3IgaSA+IG0gewoJCQltID0gbSArIHByaW1lCgkJfQoJCWlmIGkgPCBtIHsKCQkJb3V0IDwtIGkgIC8vIFNlbmQgJ2knIHRvICdvdXQnCgkJfQoJfQp9CgovLyBUaGUgcHJpbWUgc2lldmU6IERhaXN5LWNoYWluIEZpbHRlciBwcm9jZXNzZXMKZnVuYyBTaWV2ZShvdXQgY2hhbjwtIGludCkgewoJY2ggOj0gbWFrZShjaGFuIGludCkgICAgIC8vIENyZWF0ZSBhIG5ldyBjaGFubmVsCglnbyBHZW5lcmF0ZShjaCkgICAgICAgICAgLy8gTGF1bmNoIEdlbmVyYXRlIGdvcm91dGluZQoJZm9yICB7CgkJcHJpbWUgOj0gPC1jaAoJCW91dCA8LSBwcmltZQoJCWNoMSA6PSBtYWtlKGNoYW4gaW50KQoJCWdvIEZpbHRlcihjaCwgY2gxLCBwcmltZSkKCQljaCA9IGNoMQoJfQp9CgpmdW5jIG1haW4oKSB7CgljaCA6PSBtYWtlKGNoYW4gaW50KSAgICAgLy8gQ3JlYXRlIGEgbmV3IGNoYW5uZWwKCWdvIFNpZXZlKGNoKSAgICAgICAgICAgICAvLyBMYXVuY2ggU2lldmUgZ29yb3V0aW5lCgltIDo9IDMwMDAKCWZvciBpIDo9IDA7IGkgPCBtOyBpKysgewoJCXByaW1lIDo9IDwtY2gKCQlpZiBpID49IChtLTUpIHsKCQkgICAgZm10LlByaW50ZigiJTRkICIsIHByaW1lKQoJCSAgICAvL2lmIChpKzEpJTEwPT0wIHsKCQkJLy8JZm10LlByaW50bG4oIiIpCgkJICAgIC8vfQoJCX0KCX0KfQovKgozMDAwOgl0aW1lOiA0LjAyIG1lbW9yeTogNzg5NTA0IHNpZ25hbDowICAgLS0tLSBuXjIuMSAtLS0tCjI3NDA5IDI3NDI3IDI3NDMxIDI3NDM3IDI3NDQ5IAoKMjAwMDoJdGltZTogMS43NSBtZW1vcnk6IDc4OTUwNCBzaWduYWw6MCAgIC0tLS0gbl4yLjEgLS0tLQoxNzM1OSAxNzM3NyAxNzM4MyAxNzM4NyAxNzM4OSAKCjEwMDA6CXRpbWU6IDAuMzkgbWVtb3J5OiA3ODk1MDQgc2lnbmFsOjAgICAgIAo3ODc5IDc4ODMgNzkwMSA3OTA3IDc5MTkgCiov