diff options
Diffstat (limited to 'factors/type.go')
| -rw-r--r-- | factors/type.go | 27 |
1 files changed, 17 insertions, 10 deletions
diff --git a/factors/type.go b/factors/type.go index 7a0f877..b58d01c 100644 --- a/factors/type.go +++ b/factors/type.go @@ -76,6 +76,15 @@ func Type(n uint) NumberType { } } +// invariant: p must be odd and >= 3 +func nextPrime(p uint) uint { + possiblePrime := p + 2 + for !isPrime(possiblePrime) { + possiblePrime += 2 + } + return possiblePrime +} + func exponentsOrdered(n uint) bool { if n <= 2 { return true @@ -83,19 +92,17 @@ func exponentsOrdered(n uint) bool { return false } - pf := PrimeFactorize(uint(n)) + pf := PrimeFactorize(n) maxPrime := slices.Max(pf.Primes()) - lastPrime := uint(2) - for p := uint(3); p <= maxPrime; p += 2 { - if PrimeFactorize(p).Exponent(p) == 1 { - if pf.Exponent(p) > pf.Exponent(lastPrime) { - return false - } else if pf.Exponent(p) == 0 && p < maxPrime { - return false - } - lastPrime = p + for prime, prevPrime := uint(3), uint(2); prime <= maxPrime; { + if pf.Exponent(prime) > pf.Exponent(prevPrime) { + return false + } else if pf.Exponent(prime) == 0 && prime < maxPrime { + return false } + + prime, prevPrime = nextPrime(prime), prime } return true |