29 lines
853 B
Groovy
29 lines
853 B
Groovy
def factorize = { long target ->
|
|
|
|
if (target == 1) return [1L]
|
|
|
|
if (target < 4) return [1L, target]
|
|
|
|
def targetSqrt = Math.sqrt(target)
|
|
def lowfactors = (2L..targetSqrt).findAll { (target % it) == 0 }
|
|
if (lowfactors == []) return [1L, target]
|
|
def nhalf = lowfactors.size() - ((lowfactors[-1]**2 == target) ? 1 : 0)
|
|
|
|
[1] + lowfactors + (0..<nhalf).collect { target.intdiv(lowfactors[it]) }.reverse() + [target]
|
|
}
|
|
|
|
def decomposePrimes = { target ->
|
|
def factors = factorize(target) - [1]
|
|
def primeFactors = []
|
|
factors.eachWithIndex { f, i ->
|
|
if (i==0 || factors[0..<i].every {f % it != 0}) {
|
|
primeFactors << f
|
|
def pfPower = f*f
|
|
while (target % pfPower == 0) {
|
|
primeFactors << f
|
|
pfPower *= f
|
|
}
|
|
}
|
|
}
|
|
primeFactors
|
|
}
|