changeset 31113:6ee5bd9ad7cc

maint: merge stable to default
author Arun Giridhar <arungiridhar@gmail.com>
date Sat, 25 Jun 2022 16:40:58 -0400
parents d98abdd15d40 (current diff) bbb59cc6698c (diff)
children e8238ae72381
files
diffstat 1 files changed, 24 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/scripts/specfun/factor.m	Thu Jun 23 15:23:57 2022 -0400
+++ b/scripts/specfun/factor.m	Sat Jun 25 16:40:58 2022 -0400
@@ -150,23 +150,31 @@
   ## q itself will be divided by those prime factors to become smaller,
   ## unless q was prime to begin with.
 
-  ## Now go all the way to sqrt(q), where q is smaller than the original q in
-  ## most cases.
-  ##
-  ## Note: Do not try to weed out the smallprimes inside largeprimes, whether
-  ## using length(smallprimes) or max(smallprimes) -- it slows it down!
-  largeprimes = primes (sqrt (q));
-  [pf, q] = reducefactors (q, pf, largeprimes);
+  if (isprime (q))
+    ## This is an optimization for numbers like 18446744073709551566
+    ## == 2 * 9223372036854775783, where the small factors can be pulled
+    ## out easily and the remaining is prime.  This optimization reduces
+    ## 14.3 s to 1.8 ms (8000X faster) for such cases.
+    pf(end+1) = q;
+  else
+    ## Now go all the way to sqrt(q), where q is smaller than the original q in
+    ## most cases.
+    ##
+    ## Note: Do not try to weed out the smallprimes inside largeprimes, whether
+    ## using length(smallprimes) or max(smallprimes) -- it slows it down!
+    largeprimes = primes (sqrt (q));
+    [pf, q] = reducefactors (q, pf, largeprimes);
 
-  ## At this point, all prime factors <= the sqrt of the original q have been
-  ## pulled out in ascending order.
-  ##
-  ## If q = 1, then no further primes are left.
-  ## If q > 1, then q itself must be prime, and it must be the single prime
-  ## factor that was larger than the sqrt of the original q.
-  if (q > 1)
-    pf(end+1) = q;
-  endif
+    ## At this point, all prime factors <= the sqrt of the original q have been
+    ## pulled out in ascending order.
+    ##
+    ## If q = 1, then no further primes are left.
+    ## If q > 1, then q itself must be prime, and it must be the single prime
+    ## factor that was larger than the sqrt of the original q.
+    if (q > 1)
+      pf(end+1) = q;
+    endif
+  end
 
   ## At this point, all prime factors have been pulled out of q in ascending
   ## order.  There is no need to sort(pf).