1package prime
 2
 3import "math/rand"
 4
 5func RandInt(min int, max int) int {
 6	r := rand.Intn(max-min) + min
 7	return r
 8}
 9func RandPrime(min int, max int) int {
10	primes := SieveOfEratosthenes(max)
11	randN := rand.Intn(len(primes)-0) + 0
12	return primes[randN]
13}
14
15// return list of primes less than N
16func SieveOfEratosthenes(N int) (primes []int) {
17	b := make([]bool, N)
18	for i := 2; i < N; i++ {
19		if b[i] == true {
20			continue
21		}
22		primes = append(primes, i)
23		for k := i * i; k < N; k += i {
24			b[k] = true
25		}
26	}
27	return
28}
29
30func Gcd(a, b int) int {
31	var bgcd func(a, b, res int) int
32	bgcd = func(a, b, res int) int {
33		switch {
34		case a == b:
35			return res * a
36		case a%2 == 0 && b%2 == 0:
37			return bgcd(a/2, b/2, 2*res)
38		case a%2 == 0:
39			return bgcd(a/2, b, res)
40		case b%2 == 0:
41			return bgcd(a, b/2, res)
42		case a > b:
43			return bgcd(a-b, b, res)
44		default:
45			return bgcd(a, b-a, res)
46		}
47	}
48	return bgcd(a, b, 1)
49}