Golang for EulerProject

euler.go

package main

/*
import "fmt"
import "time"
*/

var MAX int = 1e7
// const MAX = 1e8

var Prime []int
var Isprime = make([]bool, MAX+1, MAX+1)
var Phi = make([]int, MAX+1, MAX+1)

type Pc struct{ p, c int }

func Genprimes() {
    for i := 2; i <= MAX; i++ {
        Isprime[i] = true
    }
    for i := 2; i <= MAX; i++ {
        if Isprime[i] {
            Prime = append(Prime, i)
            for j := i + i; j <= MAX; j += i {
                Isprime[j] = false
            }
        }
    }
}

// Genprimes() needed, about 25s for MAX = 1e8
func Genphi() {
    Phi[1] = 1
    for i := 2; i <= MAX; i++ {
        if Isprime[i] == true {
            Phi[i] = i - 1
            continue
        }
        for _, p := range Prime {
            if i%p == 0 {
                if (i/p)%p == 0 {
                    Phi[i] = Phi[i/p] * p
                } else {
                    Phi[i] = Phi[i/p] * (p - 1)
                }
                break
            }
        }
    }
}

func Powint(a, b int) (ans int) {
    ans, t := 1, a
    for b != 0 {
        if b&1 != 0 {
            ans = ans * t
        }
        t = t * t
        b >>= 1
    }
    return ans
}

func Prime_factors(n int) (pf []Pc) {
    for _, p := range Prime {
        if p >= n {
            break
        }
        if n%p == 0 {
            t := Pc{p: p}
            for n%p == 0 {
                t.c += 1
                n /= p
            }
            pf = append(pf, t)
        }
    }
    if n != 1 {
        t := Pc{p: n, c: 1}
        pf = append(pf, t)
    }
    return
}

func Divisors(n int) []int {
    pf := Prime_factors(n)
    var rec_gen func(n int) (ds []int)
    rec_gen = func(n int) (ds []int) {
        if n == len(pf) {
            ds = append(ds, 1)
        } else {
            p, c := pf[n].p, pf[n].c
            pow := 1
            pows := []int{1}
            for i := 1; i <= c; i++ {
                pow *= p
                pows = append(pows, pow)
            }
            for _, q := range rec_gen(n + 1) {
                for _, p := range pows {
                    ds = append(ds, p*q)
                }
            }
        }
        return
    }
    return rec_gen(0)
}

func Divisors_sum(n int) (ans int) {
    pf := Prime_factors(n)
    ans = 1
    for _, t := range pf {
        p, c := t.p, t.c
        ans *= (Powint(p, c+1) - 1) / (p - 1)
    }
    return
}

/*
func main() {
    t := time.Now()
    Genprimes()
    fmt.Printf("Prime done: %v\n", time.Since(t))
    Genphi()
    fmt.Printf("Phi done: %v\n", time.Since(t))
    fmt.Println(len(Prime), Prime[len(Prime)-1])
    fmt.Println(Divisors(144))
    fmt.Println(Divisors_sum(144))
    fmt.Printf("%v\n", time.Since(t))
}
*/