[BOJ] 11653 - 소인수분해

gmelan·2022년 4월 10일
0

알고리즘 트레이닝

목록 보기
4/14

풀어보기

접근

  1. 소인수분해 과정을 출력하여야 한다.
  2. 출력 결과는 오름차순이어야 한다.

소수인 인수로 인수분해를 해야 하므로 먼저 인수분해에 사용할 소수를 구하여야 한다.
... 소수는 아직까지 소수 간 규칙성이 발견되지 않았으므로 직접 나누어 보고 소수 여부를 판단하는 수 밖에 없다.

코드 1 - 정직하게 소수를 구하는 코드

문제에서 정수 NN의 범위가 상당히 크므로(1N10,000,0001 ≤ N ≤ 10,000,000), 이 코드에서 적당한 가지치기가 필요함을 짐작할 수 있다.

from sys import stdin

N = int(stdin.readline())
prime = [] # [1, N] 범위에 있는 소수를 담을 리스트

for prime_candidate in range(N):
	is_prime = True
	for divisor in range(2, prime_candidate):
    	if prime_candidate % divisor == 0:
        	is_prime = False
            break
    if is_prime:
        prime.append(prime_candidate)

print(prime)

코드 2 - 조금 더 빠르게 소수 구하기

임의의 합성수 n를 a×ba \times b (aba≤b, aa, bb는 양의 실수)꼴로 나타낸다고 할 때, aa의 최댓값은 n\sqrt n임을 알 수 있다. 따라서 최대 ii (ini ≥ \sqrt n를 만족하는 가장 작은 정수)까지만 나누어 보면 소수 여부를 판별할 수 있다.

from sys import stdin
from math import sqrt

N = int(stdin.readline())
prime = [] # [1, N] 범위에 있는 소수를 담을 리스트

for prime_candidate in range(N):
	is_prime = True
	for divisor in range(2, int(sqrt(prime_candidate)) + 1):
    	if prime_candidate % divisor == 0:
        	is_prime = False
            break
    if is_prime:
        prime.append(prime_candidate)

print(prime)

이 방법 외에도 빠르게 소수를 구할 수 있는 다른 방법들이 있지만 이번 문제에서는 제곱근을 취하는 방법을 써봤다.

이제 인수분해를 구현해보자. 사실 소수를 구하는 방법과 크게 다르지 않다. 소수 리스트 prime에서 뽑은 소수 i로 입력값 n을 하나하나 나누어 보고, 나누어 떨어진다면(=in의 인수) 나누는 방법으로 구하면 된다.
주의할 점은 오름차순으로 출력하여야 하므로, 가장 작은 소인수부터 나누어야 한다는 것이다. 또한 최종 결과가 소수인 경우(예제 3번)도 존재할 수 있으므로, 최종 결과값이 1이 아닌 경우 그 값을 출력해주어야 한다.

코드 3 - 소인수분해

from sys import stdin
from math import sqrt

n = int(stdin.readline())
prime = []

for prime_candidate in range(2, int(sqrt(n)) + 1):
    is_prime = True

    for divisor in range(2, int(sqrt(prime_candidate)) + 1):
        if prime_candidate % divisor == 0:
            is_prime = False
            break

    if is_prime:
        prime.append(prime_candidate)

divided = False

while True:
    for divisor in prime:
        if n % divisor == 0:
            n //= divisor
            print(divisor)
            divided = True
            break
    
    if not divided:
        break

    divided = False
    
if n != 1:
    print(n)

코드 4 - 좀 더 다듬은 소인수분해

from sys import stdin
from math import sqrt

n = int(stdin.readline())
prime = []

for prime_candidate in range(2, int(sqrt(n)) + 1):
    is_prime = True

    for divisor in range(2, int(sqrt(prime_candidate)) + 1):
        if prime_candidate % divisor == 0:
            is_prime = False
            break

    while is_prime and n % prime_candidate == 0:
    # prime_candidate가 소수인 경우 - 소인수분해 시작
        n //= prime_candidate
        print(prime_candidate)
 
if n != 1:
    print(n)

사실 꼭 소수 리스트를 따로 저장해둘 필요는 없다. 소수 리스트에 있는 소수 ii로 더이상 나누어지지 않을 때까지 계속 나누어주면 향후 처리에서 더이상 그 소수 ii는 필요하지 않기 때문이다.

0개의 댓글