I’ve been playing with the Go language for several weeks, and took several hours this Memorial Day weekend to do some programming in it. Here’s my standard set of prime number functions:

// prime numbers package main import ( "fmt" ) // list of primes less than n: // sieve of eratosthenes func primes(n int) (ps []int) { sieve := make([]bool, n) for i := 2; i < n; i++ { if !(sieve[i]) { ps = append(ps, i) for j := i * i; j < n; j += i { sieve[j] = true } } } return ps } // true if n is prime, else false: // trial division via 2,3,5-wheel func isPrime(n int) (bool) { wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6} w := 0 f := 2 for f*f <= n { if n % f == 0 { return false } f += wheel[w] w += 1 if w == 11 { w = 3 } } return true } // greatest common divisor of x and y: // via euclid's algorithm func gcd(x int, y int) (int) { for y != 0 { x, y = y, x % y } return x } // absolute value of x func abs(x int) (int) { if x < 0 { return -1 * x } return x } // list of prime factors of n: // trial division via 2,3,5-wheel // to 1000 followed by pollard rho func factors(n int) (fs []int) { wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6} w := 0 // wheel pointer f := 2 // current trial factor for f*f <= n && f < 1000 { for n % f == 0 { fs = append(fs, f) n /= f } f += wheel[w]; w += 1 if w == 11 { w = 3 } } if n == 1 { return fs } h := 1 // hare t := 1 // turtle g := 1 // greatest common divisor c := 1 // random number parameter for !(isPrime(n)) { for g == 1 { h = (h*h+c) % n // the hare runs h = (h*h+c) % n // twice as fast t = (t*t+c) % n // as the tortoise g = gcd(abs(t-h), n) } if isPrime(g) { for n % g == 0 { fs = append(fs, g) n /= g } } h, t, g, c = 1, 1, 1, c+1 } fs = append(fs, n) return fs } func main() { fmt.Println(primes(100)) fmt.Println(isPrime(997)) fmt.Println(isPrime(13290059)) fmt.Println(factors(13290059)) }

When run, it produces this output:

[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97] true false [3119 4261]

There’s nothing particularly tricky here: `for`

loops, arrays, and most arithmetic operations are familiar, the only thing a little bit odd is the array slice `(fs []int)`

that accumulates factors (beware: slices are apparently a source of great power in the Go language). Then I rewrote the wheel/rho factoring function for big integers, which are provided by the standard library:

// factors package main import ( "fmt" "math/big" "sort" ) // sort []*big.Int into increasing order, using sort package type BigIntSlice []*big.Int func (s BigIntSlice) Len() int { return len(s) } func (s BigIntSlice) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 } func (s BigIntSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } func (s BigIntSlice) Sort() { sort.Sort(s) } var ( zero = big.NewInt(0); one = big.NewInt(1); two = big.NewInt(2); four = big.NewInt(4); six = big.NewInt(6); wheel = [11]*big.Int{one,two,two,four,two,four,two,four,six,two,six} ) func factors(n *big.Int) (fs []*big.Int) { mod := new(big.Int) // modulus div := new(big.Int) // dividend limit := big.NewInt(1000) // switch to rho z := big.NewInt(0); // temporary storage w := 0 // wheel index f := big.NewInt(2); // trial divisor z.Mul(f, f) for z.Cmp(n) <= 0 && f.Cmp(limit) <= 0 { div.DivMod(n, f, mod) for mod.Cmp(zero) == 0 { fs = append(fs, new(big.Int).Set(f)) n.Set(div) div.DivMod(n, f, mod) } f.Add(f, wheel[w]); z.Mul(f, f) w += 1; if w == 11 { w = 3 } } if n.Cmp(one) == 0 { return fs } h := big.NewInt(1) // hare t := big.NewInt(1) // tortoise g := big.NewInt(1) // greatest common divisor c := big.NewInt(1) // random number parameter for !(n.ProbablyPrime(20)) { for g.Cmp(one) == 0 { z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z) z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z) z.Mul(t, t); z.Add(z, c); z.Mod(z, n); t.Set(z) z.Sub(t, h); z.Abs(z) g.GCD(nil, nil, z, n) } if g.ProbablyPrime(20) { div.DivMod(n, g, mod) for mod.Cmp(zero) == 0 { fs = append(fs, new(big.Int).Set(g)) n.Set(div) div.DivMod(n, g, mod) } h.Set(one) t.Set(one) g.Set(one) c.Add(c, one) } } fs = append(fs, new(big.Int).Set(n)) sort.Sort(BigIntSlice(fs)) return fs } func main() { fmt.Println(factors(big.NewInt(13290059))) x := big.NewInt(583910384809) y := big.NewInt(291648291013) x.Mul(x,y) fmt.Println(x) fmt.Println(factors(x)) }

When run, that produces this output:

[3119 4261] 170296465834288046421517 [291648291013 583910384809]

I had quite a bit of trouble remembering when functions were called in dot-notation (for instance, `div.DivMod(n, g, mod)`

sets both `div`

and `mod`

) and normal expression notation (the call to `append`

in the computation of `fs`

), and having two different meanings for `=`

and `:=`

can’t be a good thing. And it took a while for the asterisk in `(fs []*big.Int)`

to make sense (not to mention the “distributed” asterisk in the array definition). Still, I found Go mostly pleasant, rather different from the pointers and memory model of C even with a similar surface syntax.

You can run the two programs above at http://ideone.com/qxLQ0D and http://ideone.com/fXvo2R.