Skip to content

Instantly share code, notes, and snippets.

@iepathos
Last active December 17, 2015 12:19
Show Gist options
  • Save iepathos/5609054 to your computer and use it in GitHub Desktop.
Save iepathos/5609054 to your computer and use it in GitHub Desktop.
This is a very fast factorization algorithm. I've concocted it from several sources. It would be hard to find one faster than this.
from math import sqrt
"""
Fast factorization algorithm. Uses tuples instead of lists
and sqrt over exponentiation.
"""
def factors(n):
return set(x for tup in ([i, n//i]
for i in range(1, int(sqrt(n))+1) if n % i == 0) for x in tup)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment