[Python 3] Prime factorization in 14 lines

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)) # => []

reference

High-speed prime factorization with Python-for competition professionals-

Recommended Posts

[Python 3] Prime factorization in 14 lines
Prime numbers in Python
Prime number 2 in Python
Prime factorization of integers entered in Python ver.1
Prime factorization ver.2 of integers input in Python
Make python segfault in 2 lines
Python install in 2 lines @Windows
Infinite prime number generator in Python3
Make python segfault in three lines
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Meta-analysis in Python
Unittest in python
Line graphs and scale lines in python
Epoch in Python
Discord in Python
Sudoku in Python
Project Euler # 7 "1000 1st prime number" in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
I searched for prime numbers in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Draw contour lines that appear in textbooks (Python)
Read a file containing garbled lines in Python
Project Euler # 10 "sum of prime numbers" in Python
Prime number enumeration and primality test in Python
Find prime numbers in Python as short as possible