I am new to Go but not to programming. I am trying to implement a few functions on prime numbers as a way to learn. Here's my code, which you can run at http://ideone.com/qxLQ0D:
// 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))
}
That works fine. I would like to know how to initialize wheel as a constant at compile time so that it can be shared by isPrime and factors, and I would appreciate any comments on style or other aspects of my program.
I eventually want to implement some factoring algorithms on big integers, using the math/big package. But I'm having much trouble. Simplifying to just the trial division via a 2,3,5-wheel part of the algorithm, here's my code:
package main
import (
"fmt"
"math/big"
)
func factors(n big.Int) (fs []big.Int) {
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}
w := 0;
f := two;
for big.Mul(*f, *f).Cmp(n) <= 0 {
for big.Mod(n, *f).Cmp(*zero) {
fs = append(fs, *f)
n = big.Div(n, *f)
}
f = big.Add(f, wheel[w])
w += 1
if w > 11 { w = 3 }
}
fs = append(fs, n)
return fs
}
func main() {
fmt.Println(factors(*big.NewInt(13290059)))
}
That doesn't work; ideone complains that the Add, Div, Mod and Mul functions are not found. And it looks rather ugly to me, stylistically.
Please tell me how to fix my factors function.
EDIT 1: Thanks to @TClaverie, I now have a function that compiles. Now I am getting a runtime error, and ideone points to the Mul function. Once again, can anyone help? My revised code is shown below and at http://ideone.com/aVBgJg:
package main
import (
"fmt"
"math/big"
)
func factors(n *big.Int) (fs []big.Int) {
var z *big.Int
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}
w := 0
f := two
z.Mul(f, f)
for z.Cmp(n) <= 0 {
z.Mod(n, f)
for z.Cmp(zero) == 0 {
fs = append(fs, *f)
n.Div(n, f)
z.Mod(n, f)
}
f.Add(f, wheel[w])
w += 1
if w > 11 { w = 3 }
z.Mul(f, f)
}
fs = append(fs, *n)
return fs
}
func main() {
fmt.Println(factors(big.NewInt(13290059)))
}
EDIT 2: Thanks to @TClaverie, I've learned a lot about Go, and I'm close to a solution. But I still have one problem; the program
package main
import (
"fmt"
"math/big"
)
func main() {
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}
f := two; w := 0
for f.Cmp(big.NewInt(40)) < 0 {
fmt.Println(f, w, wheel)
f.Add(f, wheel[w])
w += 1; if w == 11 { w = 3 }
}
}
prints the following output, which shows that wheel is being modified in the call to Add:
2 0 [1 2 2 4 2 4 2 4 6 2 6]
3 1 [1 3 3 4 3 4 3 4 6 3 6]
6 2 [1 6 6 4 6 4 6 4 6 6 6]
12 3 [1 12 12 4 12 4 12 4 6 12 6]
16 4 [1 16 16 4 16 4 16 4 6 16 6]
32 5 [1 32 32 4 32 4 32 4 6 32 6]
36 6 [1 36 36 4 36 4 36 4 6 36 6]
What's the right way to prevent that from happening?
