Skip to content

Instantly share code, notes, and snippets.

@sooop
Last active May 4, 2021 08:11
Show Gist options
  • Save sooop/5677c02ab1f02acfa1598de63eb3ed64 to your computer and use it in GitHub Desktop.
Save sooop/5677c02ab1f02acfa1598de63eb3ed64 to your computer and use it in GitHub Desktop.
python factorizaion function
import time
from functools import wraps
def timeit(f):
@wraps(f)
def inner(*x, **y):
a = time.monotonic()
r = f(*x, **y)
b = time.monotonic()
print(f"elapsed: {b-a:.3f}s")
return r
return inner
@timeit
def factorization(n: int) -> list[tuple[int, int]]:
res = []
if n < 2:
return res
p = 2
def helper(p: int) -> int:
if p < 6:
return (3, 5, 7)[(p - 1) // 2]
t = 1 if p % 3 == 1 else 0
l = int(n ** 0.5 + 0.5) + 1
while p < l:
p, t = p + (2, 4)[t], (t + 1) % 2
if n % p == 0:
return p
return n
while n > 1:
e = 0
while n % p == 0:
n, e = n // p, e + 1
if e > 0:
res.append((p, e))
p = helper(p)
return res
@timeit
def fac(n: int) -> list[tuple[int, int]]:
"enhanced version"
res = []
if n < 2:
return res
i = 1
def helper(k: int) -> int:
if k < 3:
return k + 1
if k < 8:
return k + 2
k = k + (4 if k % 3 == 1 else 2)
l = int(n ** 0.5 + 1.5)
while k < l:
if n % k == 0:
return k
if n % (k + 2) == 0:
return k + 2
k += 6
return n
while n > 1:
e = 0
i = helper(i)
while n % i == 0:
n, e = n // i, e + 1
if e > 0:
res.append((i, e))
return res
if __name__ == "__main__":
ns = [3800651, 560411670, 10000128400406539]
for n in ns:
print(fac(n))
print(factorization(n))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment