1package prime
 2
 3import "math/rand"
 4
 5const (
 6	// MaxPrime is to get a prime value below this number
 7	MaxPrime = 2000
 8	// MinPrime is to get a prime value above this number
 9	MinPrime = 500
10)
11
12// RandInt returns a random integer between two values
13func RandInt(min int, max int) int {
14	r := rand.Intn(max-min) + min
15	return r
16}
17
18// RandPrime returns a random prime number between two values
19func RandPrime(min int, max int) int {
20	primes := SieveOfEratosthenes(max)
21	randN := rand.Intn(len(primes)-0) + 0
22	return primes[randN]
23}
24
25// SieveOfEratosthenes returns a list of primes less than N
26func SieveOfEratosthenes(N int) (primes []int) {
27	b := make([]bool, N)
28	for i := 2; i < N; i++ {
29		if b[i] == true {
30			continue
31		}
32		primes = append(primes, i)
33		for k := i * i; k < N; k += i {
34			b[k] = true
35		}
36	}
37	return
38}
39
40// Gcd returns the greatest common divisor
41func Gcd(a, b int) int {
42	var bgcd func(a, b, res int) int
43	bgcd = func(a, b, res int) int {
44		switch {
45		case a == b:
46			return res * a
47		case a%2 == 0 && b%2 == 0:
48			return bgcd(a/2, b/2, 2*res)
49		case a%2 == 0:
50			return bgcd(a/2, b, res)
51		case b%2 == 0:
52			return bgcd(a, b/2, res)
53		case a > b:
54			return bgcd(a-b, b, res)
55		default:
56			return bgcd(a, b-a, res)
57		}
58	}
59	return bgcd(a, b, 1)
60}