package main
import "fmt"
func main() {
ch := make(chan int)
go Sieve( ch) ;
n := 20000 // was: 7000 now: 10k: OK: 0.42s 20k:1.16s n^1.47
for i := 0; i < n; i++ {
prime := <-ch
if i > (n-10) {
fmt.Printf("%v ", prime)
}
}
}
func OddsFrom(from int, ch chan<- int) {
for i := from; ; i+=2 {
ch <- i
}
}
func Filter(in <-chan int, out chan<- int, prime int) {
for {
i := <-in
if i%prime != 0 {
out <- i
}
}
}
// postponed sieve by trial division - by Will Ness
func Sieve(out chan<- int) { // 2k: 0.065s !!! 4k: 0.175s n^1.43
out <- 2 // 7k: 0.357s n^1.27 (1.36) !!
out <- 3 // 8k: out-of-memory (33442 goroutines ??)
// new
out <- 5 // shallower recursion! good? YES!! 0.26s vs 0.85s for 7k!
q := 9
ps := make(chan int)
go Sieve(ps) // separate primes
p := <-ps // p=2, ps@3
p = <-ps // p=3, ps@5
nums := make(chan int)
go OddsFrom(7,nums) // was: 5
for {
n := <-nums
if n < q {
out <- n // n is prime
} else {
ch1 := make(chan int)
go Filter(nums, ch1, p) // p=3
nums = ch1
p = <-ps // 5
q = p*p // 25 !
}
}
}
/*
func Primes(out chan<- int) {
out <- 2
out <- 3
go Sieve(out)
}
func Wheel23(from int, by int, ch chan<- int) {
for i := from; ; i+=6 {
ch <- i
ch <- (i+by) // 2 or 4
}
}
func NumsFromBy(from int, by int, ch chan<- int) {
for i := from; ; i+=by {
ch <- i
}
}
func Sieve(out chan<- int) { // 2k: 0.1s 4k:0.24s n^1.26
out <- 5 // 7k: out-of-memory WTF
q := 25
ps := make(chan int)
go Sieve(ps) // separate primes supply
p := <-ps // p=5, ps@7
nums := make(chan int)
go Wheel23(7,4,nums)
for {
n := <-nums
if n < q {
out <- n // n is prime
} else {
ch1 := make(chan int)
go Filter(nums, ch1, p) // p=5
nums = ch1
p = <-ps // 7
q = p*p // 49 !
}
}
}
func Sieve(out chan<- int) {
ch := make(chan int)
go NumsFromBy(2,1,ch)
for i := 0; ; i++ {
prime := <-ch
out <- prime
ch1 := make(chan int)
go Filter(ch, ch1, prime)
ch = ch1
} // 1k: 0.27s 2k:1.32s n^2.29 !
}
func Sieve(out chan<- int) { // 1k: 0.3s 2k:1.47s n^2.29 !!
ch := make(chan int)
out <- 2
go NumsFromBy(3,2,ch)
for i := 0; ; i++ {
prime := <-ch
out <- prime
ch1 := make(chan int)
go Filter(ch, ch1, prime) // no postponement! too hasty!
ch = ch1
}
}
func Sieve(out chan<- int) { // 1.6k: out-of-memory !!???
out <- 2 // 1k: 0.16s 1.2k:0.20s n^1.22
q := 4
ps := make(chan int)
go Sieve(ps) // ok, so out-of-memory is NOT
p := <-ps // not amount of channels, but of
nums := make(chan int) // overall operations??!?
go NumsFromBy(3,1,nums)
for {
n := <-nums
if n < q {
out <- n // n is prime
} else {
ch1 := make(chan int)
go Filter(nums, ch1, p)
nums = ch1
p = <-ps
q = p*p
}
}
}
*/
cGFja2FnZSBtYWluCgppbXBvcnQgImZtdCIKCmZ1bmMgbWFpbigpIHsKICBjaCA6PSBtYWtlKGNoYW4gaW50KQogIGdvIFNpZXZlKCBjaCkgOwogIG4gOj0gMjAwMDAgICAgICAgICAgICAgICAvLyB3YXM6IDcwMDAgbm93OiAxMGs6IE9LOiAwLjQycyAyMGs6MS4xNnMgbl4xLjQ3CiAgZm9yIGkgOj0gMDsgaSA8IG47IGkrKyB7CiAgICBwcmltZSA6PSA8LWNoCiAgICBpZiBpID4gKG4tMTApIHsKICAgIAlmbXQuUHJpbnRmKCIldiAiLCBwcmltZSkKICAgIAl9CiAgfQp9CgpmdW5jIE9kZHNGcm9tKGZyb20gaW50LCBjaCBjaGFuPC0gaW50KSB7CiAgICBmb3IgaSA6PSBmcm9tOyA7IGkrPTIgewogICAgICAgIGNoIDwtIGkKICAgIH0KfQoKZnVuYyBGaWx0ZXIoaW4gPC1jaGFuIGludCwgb3V0IGNoYW48LSBpbnQsIHByaW1lIGludCkgewogICAgZm9yIHsKICAgICAgICBpIDo9IDwtaW4KICAgICAgICBpZiBpJXByaW1lICE9IDAgewogICAgICAgICAgICBvdXQgPC0gaQogICAgICAgIH0KICAgIH0KfQogICAgICAgICAgICAgICAgICAgICAgIC8vIHBvc3Rwb25lZCBzaWV2ZSBieSB0cmlhbCBkaXZpc2lvbiAtIGJ5IFdpbGwgTmVzcwpmdW5jIFNpZXZlKG91dCBjaGFuPC0gaW50KSB7ICAgICAvLyAyazogMC4wNjVzICEhISAgIDRrOiAwLjE3NXMgIG5eMS40MwogIG91dCA8LSAyICAgICAgICAgICAgICAgICAgICAgICAvLyA3azogMC4zNTdzICBuXjEuMjcgKDEuMzYpICEhCiAgb3V0IDwtIDMgICAgICAgICAgICAgICAgICAgICAgIC8vIDhrOiBvdXQtb2YtbWVtb3J5ICgzMzQ0MiBnb3JvdXRpbmVzID8/KQogICAvLyBuZXcKICBvdXQgPC0gNSAgICAvLyBzaGFsbG93ZXIgcmVjdXJzaW9uISBnb29kPyBZRVMhISAwLjI2cyB2cyAwLjg1cyBmb3IgN2shCiAgcSA6PSA5CiAgcHMgOj0gbWFrZShjaGFuIGludCkKICBnbyBTaWV2ZShwcykgICAgICAgICAgICAgICAgICAgLy8gc2VwYXJhdGUgcHJpbWVzCiAgcCA6PSA8LXBzICAgICAgICAgICAgICAgICAgICAgIC8vIHA9MiwgcHNAMwogIHAgPSA8LXBzICAgICAgICAgICAgICAgICAgICAgICAvLyBwPTMsIHBzQDUKICBudW1zIDo9IG1ha2UoY2hhbiBpbnQpCiAgZ28gT2Rkc0Zyb20oNyxudW1zKSAgICAgLy8gd2FzOiA1CiAgZm9yIHsKICAgIG4gOj0gPC1udW1zCiAgICBpZiBuIDwgcSB7CiAgICAJb3V0IDwtIG4gICAgICAgICAgICAgICAgIC8vIG4gaXMgcHJpbWUKICAgIH0gZWxzZSB7CiAgICAgICAgY2gxIDo9IG1ha2UoY2hhbiBpbnQpCiAgICAgICAgZ28gRmlsdGVyKG51bXMsIGNoMSwgcCkgIC8vIHA9MwogICAgICAgIG51bXMgPSBjaDEKICAgIAlwID0gPC1wcyAgICAgICAgICAgICAgICAgLy8gNQogICAgCXEgPSBwKnAgICAgICAgICAgICAgICAgICAvLyAyNSAhCiAgICB9CiAgfQp9Ci8qCmZ1bmMgUHJpbWVzKG91dCBjaGFuPC0gaW50KSB7CglvdXQgPC0gMgogICAgb3V0IDwtIDMKCWdvIFNpZXZlKG91dCkKfQoKZnVuYyBXaGVlbDIzKGZyb20gaW50LCBieSBpbnQsIGNoIGNoYW48LSBpbnQpIHsKICAgIGZvciBpIDo9IGZyb207IDsgaSs9NiB7CiAgICAgICAgY2ggPC0gaQogICAgICAgIGNoIDwtIChpK2J5KSAgLy8gMiBvciA0CiAgICB9Cn0KZnVuYyBOdW1zRnJvbUJ5KGZyb20gaW50LCBieSBpbnQsIGNoIGNoYW48LSBpbnQpIHsKICAgIGZvciBpIDo9IGZyb207IDsgaSs9YnkgewogICAgICAgIGNoIDwtIGkKICAgIH0KfQoKZnVuYyBTaWV2ZShvdXQgY2hhbjwtIGludCkgeyAgICAgLy8gMms6IDAuMXMgIDRrOjAuMjRzICBuXjEuMjYKICBvdXQgPC0gNSAgICAgICAgICAgICAgICAgICAgICAgLy8gN2s6IG91dC1vZi1tZW1vcnkgV1RGCiAgcSA6PSAyNQogIHBzIDo9IG1ha2UoY2hhbiBpbnQpCiAgZ28gU2lldmUocHMpICAgICAgICAgICAgICAgICAgIC8vIHNlcGFyYXRlIHByaW1lcyBzdXBwbHkKICBwIDo9IDwtcHMgICAgICAgICAgICAgICAgICAgICAgLy8gcD01LCBwc0A3CiAgbnVtcyA6PSBtYWtlKGNoYW4gaW50KQogIGdvIFdoZWVsMjMoNyw0LG51bXMpCiAgZm9yIHsKICAgIG4gOj0gPC1udW1zCiAgICBpZiBuIDwgcSB7CiAgICAJb3V0IDwtIG4gICAgICAgICAgICAgICAgIC8vIG4gaXMgcHJpbWUKICAgIH0gZWxzZSB7CiAgICAgICAgY2gxIDo9IG1ha2UoY2hhbiBpbnQpCiAgICAgICAgZ28gRmlsdGVyKG51bXMsIGNoMSwgcCkgIC8vIHA9NQogICAgICAgIG51bXMgPSBjaDEKICAgIAlwID0gPC1wcyAgICAgICAgICAgICAgICAgLy8gNwogICAgCXEgPSBwKnAgICAgICAgICAgICAgICAgICAvLyA0OSAhCiAgICB9CiAgfQp9CgpmdW5jIFNpZXZlKG91dCBjaGFuPC0gaW50KSB7CiAgY2ggOj0gbWFrZShjaGFuIGludCkKICBnbyBOdW1zRnJvbUJ5KDIsMSxjaCkKICBmb3IgaSA6PSAwOyA7IGkrKyB7CiAgICBwcmltZSA6PSA8LWNoCiAgICBvdXQgPC0gcHJpbWUKICAgIGNoMSA6PSBtYWtlKGNoYW4gaW50KQogICAgZ28gRmlsdGVyKGNoLCBjaDEsIHByaW1lKQogICAgY2ggPSBjaDEKICB9ICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIDFrOiAwLjI3cyAyazoxLjMycyBuXjIuMjkgIQp9CgpmdW5jIFNpZXZlKG91dCBjaGFuPC0gaW50KSB7ICAgLy8gMWs6IDAuM3MgMms6MS40N3Mgbl4yLjI5ICEhCiAgY2ggOj0gbWFrZShjaGFuIGludCkKICBvdXQgPC0gMgogIGdvIE51bXNGcm9tQnkoMywyLGNoKQogIGZvciBpIDo9IDA7IDsgaSsrIHsKICAgIHByaW1lIDo9IDwtY2gKICAgIG91dCA8LSBwcmltZQogICAgY2gxIDo9IG1ha2UoY2hhbiBpbnQpCiAgICBnbyBGaWx0ZXIoY2gsIGNoMSwgcHJpbWUpICAgLy8gbm8gcG9zdHBvbmVtZW50ISB0b28gaGFzdHkhCiAgICBjaCA9IGNoMQogIH0KfQoKZnVuYyBTaWV2ZShvdXQgY2hhbjwtIGludCkgeyAgICAgLy8gMS42azogb3V0LW9mLW1lbW9yeSAhIT8/PwogIG91dCA8LSAyICAgICAgICAgICAgICAgICAgICAgICAvLyAxazogMC4xNnMgIDEuMms6MC4yMHMgbl4xLjIyCiAgcSA6PSA0CiAgcHMgOj0gbWFrZShjaGFuIGludCkKICBnbyBTaWV2ZShwcykgICAgICAgICAgICAgICAgICAgLy8gb2ssIHNvIG91dC1vZi1tZW1vcnkgaXMgTk9UCiAgcCA6PSA8LXBzICAgICAgICAgICAgICAgICAgICAgIC8vIG5vdCBhbW91bnQgb2YgY2hhbm5lbHMsIGJ1dCBvZgogIG51bXMgOj0gbWFrZShjaGFuIGludCkgICAgICAgICAvLyBvdmVyYWxsIG9wZXJhdGlvbnM/PyE/CiAgZ28gTnVtc0Zyb21CeSgzLDEsbnVtcykKICBmb3IgewogICAgbiA6PSA8LW51bXMKICAgIGlmIG4gPCBxIHsKICAgIAlvdXQgPC0gbiAgICAgICAgICAgICAgICAgLy8gbiBpcyBwcmltZQogICAgfSBlbHNlIHsKICAgICAgICBjaDEgOj0gbWFrZShjaGFuIGludCkKICAgICAgICBnbyBGaWx0ZXIobnVtcywgY2gxLCBwKQogICAgICAgIG51bXMgPSBjaDEKICAgIAlwID0gPC1wcwogICAgCXEgPSBwKnAKICAgIH0KICB9Cn0KKi8=