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