Factors of an integer: Difference between revisions

Content added Content deleted

Inline

@@ Line 5,577: / Line 5,577: @@
 Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)):
-<syntaxhighlight lang="python">>>> from math import sqrt
+<syntaxhighlight lang="python">from math import isqrt
->>> def factor(n):
+def factor(n):
-      factors = set()
+    factors1, factors2 = [], []
-      for x in range(1, int(sqrt(n)) + 1):
+    for x in range(1, isqrt(n)):
         if n % x == 0:
-          factors.add(x)
+            factors1.append(x)
-          factors.add(n//x)
+            factors2.append(n // x)
+    x += 1
-      return sorted(factors)
+    if x * x == n:
+        factors1.append(x)
->>> for i in (45, 53, 64): print( "%i: factors: %s" % (i, factor(i)) )
+    factors1.extend(reversed(factors2))
+    return factors1
+for i in 45, 53, 64:
+    print("%i: factors: %s" % (i, factor(i)))</syntaxhighlight><pre>
 : factors: [1, 3, 5, 9, 15, 45]
 : factors: [1, 53]
-: factors: [1, 2, 4, 8, 16, 32, 64]</syntaxhighlight>
+: factors: [1, 2, 4, 8, 16, 32, 64]</pre>
 More efficient when factoring many numbers: