소인수분해

이해하기 쉬운 코드

from math import sqrt

# 소수 판별 함수
def isPrime(num):
	for i in range(2, int(sqrt(num)) + 1):
		if num % i == 0:
			return False
	return True

# 소수를 찾는 함수
def findPrimes(n):
    primes = []
    for i in range(2, (n//2)+1):
        if isPrime(i):
            primes.append(i)
    return primes

# 소인수 분해 함수
def factorization(n):
    factors = []
    primes = findPrimes(n)
    for i in primes:
        while (n % i == 0):
            factors.append(i)
            n //= i
    return factors

n이 입력되면 1부터 n까지 소수를 찾고, 그 소수들로 n을 모듈러 연산해 0이 되는 값(소인수)을 찾는다.

소인수를 찾았다면 그 수로 n을 나눈 몫으로 다시 반복한다. 모듈러 연산값이 0이 아니라면 다음 소수로 넘어간다.

 

 

조금 복잡

from math import sqrt

def factorization(n):
        factor = 2
        factors = []
        
        while (factor <= sqrt(n)):
            while (n % factor == 0):
                factors.append(factor)
                n //= factor
            factor += 1

        if n > 1:
            factors.append(n)
            
        return factors

factor를 2로 지정한다.

n의 제곱근보다 factor가 크게 되면 반복이 멈춘다. -> 이 과정 때문에 위 코드보다 빠름

소인수를 찾는 방법은 위 코드와 동일하다.

안쪽 반복문이 종료되면 factor를 1 증가시킨다.

바깥쪽 반복문이 종료된 후 n이 1보다 크다면 그 수도 소인수로 포함시킨다.