package kata

import (
	"fmt"
	"math"
	"strings"
)

/*
trimPrimes removes the impossible primes from the list against which to check.
  - primes: the current list
  - low: the lowest possible value for a valid prime
  - n: the maximum possible value for a valid prime
*/

func trimPrimes(primes []int, low, high int) []int {
	var res []int
	lowIndex, highIndex := 0, int(math.Ceil(math.Sqrt(float64(high))))
	for i, prime := range primes {
		if prime < low {
			lowIndex = i
		}
		if prime > highIndex {
			highIndex = i
			break
		}
	}
	if highIndex > len(primes) {
		res = primes[lowIndex:]
	} else {
		res = primes[lowIndex:highIndex]
	}
	return res
}

func trialDivision(n int) []int {
	limit := int(math.Ceil(math.Sqrt(float64(n))))
	primes := Primes(limit)
	var divisors []int
	for _, prime := range primes {
		for n > 1 {
			if n%prime == 0 {
				divisors = append(divisors, prime)
				n /= prime
				primes = trimPrimes(primes, prime, n)
				continue
			}
			primes = trimPrimes(primes, prime+2, n)
			break
		}
	}
	if n > 1 {
		divisors = append(divisors, n)
	}
	return divisors
}

func format(curr, power int) string {
	if power == 1 {
		return fmt.Sprintf("(%d)", curr)
	} else {
		return fmt.Sprintf("(%d**%d)", curr, power)
	}
}

func PrimeFactors(n int) string {
	if n <= 1 {
		return ""
	}
	factors := trialDivision(n)
	var rows []string
	curr := 1
	power := 1
	for _, divisor := range factors {
		if divisor == curr {
			power++
		} else {
			rows = append(rows, format(curr, power))
			curr = divisor
			power = 1
		}
	}
	rows = append(rows, format(curr, power))
	res := strings.Join(rows[1:], "")
	return res
}