package kata

import (
	"fmt"
	"math/big"
)

// Documented as exact up to 2^64.
func isPrime(n int) bool {
	return big.NewInt(int64(n)).ProbablyPrime(1)
}

/*
Gap returns the first pair of two prime numbers spaced with the specified gap,
if one exists. Otherwise, it returns nil.

 - gap >= 2 is the gap we are looking for
 - start > 2 is the start of the search, inclusive
 - end >= start is the end of the search, inclusive
*/
func Gap(gap, start, end int) []int {
	var res []int
	fmt.Printf("%d %d-%d\n", gap, start, end)
	// Handle degenerate cases first.
	if gap%2 == 1 {
		return res
	}
	if start%2 == 0 {
		start++
	}
	if start >= end {
		return res
	}
	var low, high int
External:
	for low = start; low <= end-gap; low += 2 {
		high = low + gap
		if !isPrime(low) || !isPrime(high) {
			continue
		}
		// We have a prime pair. Is it a gap ?
		for mid := low + 2; mid < high; mid++ {
			// If there is a smaller pair, it's not a gap.
			if isPrime(mid) {
				continue External
			}
		}
		// It's a gap!
		return []int{low, high}
	}
	return nil
}