Surprisingly, there is no prime factorization in the Python standard library. I wrote it simply using Counter. In 14 lines from the top.
prime_factorization.py
from math import sqrt
from collections import Counter
def prime_factorization(n):
counter = Counter()
for i in range(2, int(sqrt(n)) + 1):
while n % i == 0:
n //= i
counter[i] += 1
if n != 1:
counter[n] += 1
return list(counter.items())
def prime_factors(n):
return set(map(lambda x: x[0], prime_factorization(n)))
if __name__ == '__main__':
# 2020 = 2^2 * 5^1 * 101^1
print(prime_factorization(2020)) # => [(2, 2), (5, 1), (101, 1)]
print(prime_factors(2020)) # => {2, 101, 5}
#If 1 returns a list from
print(prime_factorization(1)) # => []
High-speed prime factorization with Python-for competition professionals-
Recommended Posts