파이썬에서 소인수 찾기

1. 소인수 분해 개요
2. 파이썬에서 소인수를 찾기 위한 다양한 접근법

이 튜토리얼은 Python에서 소인수 분해를 수행하는 방법을 보여줍니다.

소인수 분해 개요

수학에서 약수는 주어진 수를 나누고 나머지를 0으로 남겨둘 수 있는 수입니다.

소수는 하나와 숫자 자체의 두 가지 요소만 있는 고유한 숫자입니다. 이러한 숫자의 몇 가지 예는 3,7,11,13 등입니다.

소인수 분해는 원래 숫자를 구성하기 위해 곱해지는 모든 소수를 찾는 것을 말합니다. 숫자 6의 간단한 예를 생각해 볼 수 있습니다.

이 숫자를 소인수분해하면 2와 3의 두 인수가 생성됩니다.

파이썬에서 소인수를 찾기 위한 다양한 접근법

다양한 방법으로 지정된 숫자의 소인수를 찾을 수 있습니다. 이 문서에서는 아래에 나열된 세 가지 방법을 설명합니다.

• 커스텀 함수 생성
• 에라토스테네스의 체 사용
• primefac 모듈 사용

Python에서 사용자 지정 함수를 만드는 것부터 시작하겠습니다.

소인수 분해를 수행하는 사용자 지정 함수

수학에서 가장 기본적인 소인수 분해 방법은 반복 나눗셈입니다. 숫자를 소수로 반복해서 나눕니다. 중첩 루프를 사용하여 Python에서 이를 구현할 수 있습니다.

첫 번째 루프는 숫자가 소수인지 여부를 결정합니다. 두 번째 루프는 이 소수와 주어진 숫자를 나눕니다.

나머지가 0이면 목록에 소수를 추가합니다. 이 함수는 최종 목록을 반환합니다. 아래 코드를 참조하십시오.

def p_factorization(n):
    i = 2
    lst = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            lst.append(i)
    if n > 1:
        lst.append(n)
    return lst


print(p_factorization(20))

출력:

[2, 2, 5]

위의 예에서 20의 소인수 분해를 반환했습니다. 나눗셈을 위한 // 연산자는 반환된 나머지가 정수임을 확인합니다.

에라토스테네스의 체를 사용하여 소인수 분해를 수행합니다.

에라토스테네스의 체 알고리즘은 주어진 숫자 아래의 모든 소수를 반환합니다.

주어진 숫자보다 작은 값을 표시하고 주어진 숫자보다 작은 모든 소수를 반환하기 위해 소수의 제곱으로 나눌 수 있습니다.

Python에서 소인수 분해를 수행하는 데 사용할 수 있습니다. 먼저 필요한 숫자 아래의 소수를 찾은 다음 주어진 숫자로 나누어 소인수 분해를 확인합니다.

예제로 다음 코드 펜스를 참조하십시오.

def sieve_of_erast(number):
    maximum = number + 1
    d = dict()
    for i in range(2, maximum):
        d[i] = True

    for i in d:
        factors = range(i, maximum, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


def p_factorization(number):
    x = number
    res = []
    lst = sieve_of_erast(number)
    i = 0
    while i < len(lst):
        if x % lst[i] == 0:
            x = x // lst[i]
            res.append(lst[i])
            i = 0
            if x == 1:
                break
        else:
            i = i + 1
    return res


print(p_factorization(20))

출력:

[2, 2, 5]

위의 코드 예제에서는 먼저 에라토스테네스의 체를 구현하여 20 아래의 소수를 찾는 함수를 만듭니다.

그런 다음 이 소수 목록을 사용하여 동일한 소인수 분해를 반환하는 다른 함수를 만듭니다.

primefac 모듈을 사용하여 소인수 분해 수행

primefac 모듈은 소수에 관한 계산을 수행하는 데 사용됩니다. 광범위한 계산을 효율적으로 처리할 수 있습니다.

소인수 분해를 위해 이 모듈의 primefac() 함수를 사용할 수 있습니다. list 생성자를 사용하여 목록으로 변환할 수 있는 생성기 개체를 반환합니다.

아래 코드를 참조하십시오.

import primefac

print(list(primefac.primefac(20)))

출력:

[2, 2, 5]