# [libmath-prime-util-perl] 24/54: Add perfect power test in factoring

```This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.38
in repository libmath-prime-util-perl.```
```
Author: Dana Jacobsen <d...@acm.org>
Date:   Tue Feb 11 17:22:04 2014 -0800

Add perfect power test in factoring
---
Changes  |  7 +++++++
factor.c | 22 ++++++++++++++++++++++
2 files changed, 29 insertions(+)

diff --git a/Changes b/Changes
index fedc152..eb94700 100644
--- a/Changes
+++ b/Changes
@@ -6,6 +6,13 @@ Revision history for Perl module Math::Prime::Util

- is_power         Returns max k if n=p^k.  See Pari 2.4.x.

+    [FUNCTIONALITY AND PERFORMANCE]
+
+    - Factoring powers is much faster.
+
+    [OTHER]
+
+    - Added some Project Euler examples.

0.37  2014-01-26

diff --git a/factor.c b/factor.c
index cce32fb..f23c227 100644
--- a/factor.c
+++ b/factor.c
@@ -81,6 +81,28 @@ int factor(UV n, UV *factors)
factors[nfactors++] = n;
return nfactors;
}
+  /* Perfect powers.  Factor root only once. */
+  {
+    int i, j, k = powerof(n);
+    if (k > 1) {
+      UV p = (k == 2) ? isqrt(n) : (UV) (pow(n, 1.0/(double)k) + 0.01);
+      UV pk = p*p;
+      for (i = 2; i < k; i++)  pk *= p;
+      MPUassert( pk == n, "incorrect root in factor" );
+      if (is_prob_prime(p)) {
+        for (j = 0; j < k; j++)
+          factors[nfactors++] = p;
+        return nfactors;
+      } else {
+        int nsmallfactors = nfactors;
+        nfactors = factor(p, factors+nsmallfactors);
+        for (i = nfactors; i >= 0; i--)
+          for (j = 0; j < k; j++)
+            factors[nsmallfactors+k*i+j] = factors[nsmallfactors+i];
+        return nsmallfactors + k*nfactors;
+      }
+    }
+  }

{
UV tofac_stack[MPU_MAX_FACTORS+1];

--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
```