// 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))
}