p.go

package main
import "fmt"
import "sync"
import "math"
import "runtime"
import "sync/atomic"

//Dead slow
func pseq(max int) chan int{
    out := make(chan int)
    var filter func(chan int)
    filter = func(in chan int) {
        n := <-in
        out <- n
        //fmt.Println(n)
        var next chan int
        if n*n >= max {
            next = out
        }else{
            next = make (chan int)
            go filter(next)
        }
        for {
            x,ok := <-in
            if ok {
                if x%n!=0 {
                    next<-x
                }
            } else {
                close(next)
                return
            }
        }
    }

    in := make(chan int)
    go filter(in)
    go func() {
        for i:=2;i<max;i++{
            in<-i
        }
        close(in)
    }()
    return out
}

//Faster
func pseq2(max int) chan int {
    out := make(chan int)
    arr := make([]bool,max+1)
    arr[0]=true
    arr[1]=true
    var wg sync.WaitGroup
    var take func(int)
    take=func(n int){
        defer wg.Done()
        if n*n > max {
            return
        }
        wg.Add(1)
        go take(n+1)
        for i:=n*2;i<max;i+=n{
            arr[i] = true
        }
    }
    wg.Add(1)
    go take(2)
    wg.Wait()
    go func(){
        for i:=2;i<max;i++{
            if arr[i] == false{
                out<-i;
            }
        }
        close(out)
    }()
    return out
}

//Even faster
func pseq3(max int) chan int {
    fmt.Println(max)
    out := make(chan int)
    if(max <= 2) {
        go func(){
            out<-2
            close(out)
        }()
        return out
    }
    arr := make([]bool,max+1)
    arr[0]=true
    arr[1]=true
    var wg sync.WaitGroup
    ch := pseq3( int( math.Sqrt( float64( max ) ) ) )
    var worker func() = func(){
        defer wg.Done()
        for {
            n,ok := <-ch
            if !ok {
                return
            }
            for i:=n*2;i<max;i+=n{
                arr[i] = true
            }
            //fmt.Println(n)
        }
    }

    for i:=0;i<runtime.NumCPU();i++ {
        wg.Add(1)
        go worker()
    }
    wg.Wait()
    //fmt.Println("OK")
    go func(){
        for i:=2;i<max;i++{
            if arr[i] == false{
                out<-i;
            }
        }
        close(out)
    }()
    return out
}

//Even more faster
func pseq4(max int) chan int {
    fmt.Println(max)
    out := make(chan int,10)
    if(max <= 2) {
        go func(){
            out<-2
            close(out)
        }()
        return out
    }
    arr := make([]bool,max+1)
    arr[0]=true
    arr[1]=true
    var wg sync.WaitGroup
    ch := pseq3( int( math.Sqrt( float64( max ) ) ) )
    var worker func() = func(){
        defer wg.Done()
        for {
            n,ok := <-ch
            if !ok {
                return
            }
            for i:=n*2;i<max;i+=n{
                arr[i] = true
            }
            //fmt.Println(n)
        }
    }

    for i:=0;i<runtime.NumCPU();i++ {
        wg.Add(1)
        go worker()
    }
    wg.Wait()
    //fmt.Println("OK")
    if max < 10000 {
        go func(){
            for i:=2;i<max;i++{
                if arr[i] == false{
                    out<-i;
                }
            }
            close(out)
        }()
    }else{
        n := max/runtime.NumCPU()
        c := int32(0)
        for i:=2;i<max;i+=n{
            atomic.AddInt32(&c,1)
            go func(s,e int){
                //fmt.Println(s,e)
                for j:=s;j<e;j++{
                    if arr[j] == false{
                        out<-j;
                    }
                }
                cc := atomic.AddInt32(&c,-1)
                if(cc==0){
                    close(out)
                }
            }(i,imin(max,i+n))
        }
    }
    return out
}

func main() {
    runtime.GOMAXPROCS(runtime.NumCPU())
    p := pseq4(100000000)
    x := 0
    for {
        _,ok := <-p
        if ok {
            x++
        }else{
            fmt.Println(x)
            return
        }
    }
}

func imin(a,b int) int {
    if a<b {
        return a
    }
    return b
}