[백준 11653] 소인수분해 with Python

문제 링크

www.acmicpc.net/problem/11653

11653번: 소인수분해

풀이

import sys

n = int(sys.stdin.readline())
if n > 1:
    nums = [x for x in range(2, int(n**0.5)+1)]
    primes = []
    while nums:
        prime = nums[0]
        for i in nums:
            if i % prime == 0:
                nums.remove(i)
                if prime not in primes:
                    primes.append(prime)
    while n > 1:
        if primes:
            if n % primes[0] == 0:
                n //= primes[0]
                print(primes[0])
            else:
                primes = primes[1:]
        else:
            print(n)
            break

먼저 자연수 N의 제곱근 이하의 소수들을 찾는다. 제곱근까지만 찾는 이유는 N이 소수가 아닐 때 N = a * b(a는 소수, b > 1)이고, 2부터 제곱근 이하까지 소수가 없다면 N = a * b는 성립할 수 없기 때문이다. 왜냐하면 N을 36이라 할 때, 1*36, 2*18, 3*12, 4*9, 6*6, 9*4, 12*3, 18*2, 36*1 이런식으로 약수의 곱으로 나타낼 때 중간(제곱근)을 기점으로 이미 등장한 약수가 다시 반복되기 때문에, 제곱근 이하의 소수가 존재하지 않으면 그 뒷부분도 존재하지 않으므로 소수이다.

 

작은 소수부터 시작해서 N이 1이 될 때까지 나눈다. 해당 소수로 나누어 떨어지지 않으면 다음으로 큰 소수로 넘어간다. 가장 큰 소수까지 나눴는데도 N이 1이 되지 않는다면 N은 N제곱근보다 큰 소수가 되므로 N을 출력한다.