1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 |
- 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
- }
|