- 소인수분해 과정을 출력하여야 한다.
- 출력 결과는 오름차순이어야 한다.
소수인 인수로 인수분해를 해야 하므로 먼저 인수분해에 사용할 소수를 구하여야 한다.
... 소수는 아직까지 소수 간 규칙성이 발견되지 않았으므로 직접 나누어 보고 소수 여부를 판단하는 수 밖에 없다.
문제에서 정수 의 범위가 상당히 크므로(), 이 코드에서 적당한 가지치기가 필요함을 짐작할 수 있다.
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)
임의의 합성수 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
을 하나하나 나누어 보고, 나누어 떨어진다면(=i
가n
의 인수) 나누는 방법으로 구하면 된다.
주의할 점은 오름차순으로 출력하여야 하므로, 가장 작은 소인수부터 나누어야 한다는 것이다. 또한 최종 결과가 소수인 경우(예제 3번)도 존재할 수 있으므로, 최종 결과값이 1이 아닌 경우 그 값을 출력해주어야 한다.
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)
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)
사실 꼭 소수 리스트를 따로 저장해둘 필요는 없다. 소수 리스트에 있는 소수 로 더이상 나누어지지 않을 때까지 계속 나누어주면 향후 처리에서 더이상 그 소수 는 필요하지 않기 때문이다.