산술의 기본정리와 인수분해 알고리즘 예제

산술의 기본정리

Statement:

모든 자연수는 순서를 고려하지 않는다면 유일하게 소인수분해된다.

History:

역사적으로는 유클리드가 최초로 예상함.

가우스가 처음으로 증명 - 1798년, in his Disquisitiones Arithmeticae

수학적 일반화 최종버전(2018년 현재):

UFD(Unique Factorization Domain) - 추상대수 or Abstract Algebra

파이썬 예제

Input: 자연수를 입력한다

Output: 소인수와 그 지수가 순서쌍으로 나열된다.

Source Code:

def factorInteger(n):
    # n 이하의 소수 목록을 작성한다.
    primes = {k for k in range(2,n+1) if len({m for m in range(2,k) if k%m == 0}) == 0 }

    factors = []   # 소인수 목록을 저장할 변수

    # 소인수분해
    for p in primes:
        count = 0
        while n % p == 0:
            n /= p
            count += 1
        if count != 0:
            factors.append((p, count))
    return factors

n = int(input())
print(factorInteger(n))

첨언: 위 알고리즘은 매번 새로 소수 목록을 작성해서 숫자가 커질 수록 시간이 급속도로 늘어난다. 그래서, 소수목록을 따로 파일로 작성해뒀다가 빼서 쓰면 훨씬 빠른 속도로 계산을 끝낼 수 있다.