분류

  • 소수 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def factorization(n): 
    d = 2
    f = []
    
    while d <= n ** 0.5:
        if n % d == 0:
            f.append(d) 
            n //= d 
        else: 
            d += 1
    
    if n > 1:
        f.append(n)
        
    return f

설명

소인수 분해는 1보다 큰 자연수를 소수인 인수들만의 곱으로 나타내는 것이다.

소인수는 어떤 수의 제곱근 이내의 소인수들의 곱으로 표현할 수 있다.