728x90

 

 

백준 11653번: 소인수 분해

문제 바로 가기

📌 문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

 

 

📝 문제 접근 방법

문제 분석

문제의 목표는 주어진 숫자 $N$을 소인수분해하여 모든 소인수를 출력하는 것입니다. 소인수분해란 $N$을 소수들의 곱으로 표현하는 것을 의미합니다. 예를 들어 $N = 72$는 $2 \times 2 \times 2\times 3 \times 3$으로 표현됩니다. 

 

문제에서 주어진 제약 조건은 다음과 같습니다. $N$의 범위는 $1 \leq N \leq 10,000,000$입니다. $N = 1$인 경우에는 아무것도 출력하지 않습니다. 출력은 소인수를 한 줄에 하나씩 오름차순으로 출력합니다. 

 

 

아이디어

$N$의 소인수는 모두 소수입니다. 따라서 소수만을 탐색하여 $N$을 나누는 방식이 불필요한 연산을 줄이는 가장 효율적인 방법입니다.



$N$의 소인수는 항상 $\sqrt{N}$ 이하에 존재합니다. 이는 $N$이 합성수라면 $N = a \times b$의 형태로 나타낼 수 있고 $a$와 $b$ 중 적어도 하나는 반드시 $\sqrt{N}$ 이하의 값을 갖기 때문입니다. 따라서 $\sqrt{N}$ 까지만 탐색해도 충분합니다. 



효율적인 소수 탐색을 위해 $\sqrt{N}$까지의 소수를 구하는 데 에라토스테네스의 체를 사용합니다. 이렇게 구한 소수 리스트를 활용하면 소인수분해 과정에서 소수 여부를 빠르고 정확하게 확인할 수 있습니다.



소인수 분해 과정은 다음과 같이 진행됩니다. $N$을 소수 리스트의 값으로 나누면서 나머지가 0인 경우 해당 소수를 소인수로 출력합니다. 이후 $N$을 해당 소수로 나눈 몫으로 갱신하며 계속 진행합니다. $\sqrt{N}$까지 나누는 작업이 끝난 뒤 남은 $N > 1$이라면 이는 소수로 간주하여 마지막으로 출력합니다.

 

 

 

👩‍💻 나의 답안

 

1. 소수 리스트 생성 

def isPrime(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return is_prime
  • 에라토스테네스의 체를 사용하여 소수 리스트를 생성합니다. is_prime 리스트에서 소수는 True, 소수가 아닌 숫자는 False로 표시됩니다.
  • 소수는 $n$의 소인수만 탐색하므로 되므로 $\sqrt{n}$까지만 계산합니다.

 

 

2. 소인수분해

def prime_factorization(n):
    limit = int(math.sqrt(n)) + 1
    prime_list = isPrime(limit)

    for i in range(2, len(prime_list)):
        if prime_list[i]:
            while n % i == 0:
                print(i)
                n //= i

    if n > 1: 
        print(n)
  • 소수 리스트를 사용하여 $n$을 소인수분해합니다.
    1. 소수 $i$를 순회하며 $n % i == 0$이면 $i$는 $n$의 소인수입니다.
    2. 나눌 수 있을 때까지 $n$을 $i$로 나누고 매번 $i$로 출력합니다.
    3. $n > 1$인 경우 이는 더 이상 나눌 수 없는 소수이므로 출력합니다.

 

 

3. 전체 코드

import math

def isPrime(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return is_prime

def prime_factorization(n):
    limit = int(math.sqrt(n)) + 1
    prime_list = isPrime(limit)

    for i in range(2, len(prime_list)):
        if prime_list[i]:
            while n % i == 0:
                print(i)
                n //= i

    if n > 1: 
        print(n)

n = int(input())
if n > 1:
    prime_factorization(n)

 

 

 

 

🔍 다른 사람 답안

def prime_factorization(n):
    i = 2
    factors = []
    while i * i <= n: 
        while n % i == 0:  
            factors.append(i)
            n //= i
        i += 1
    if n > 1: 
        factors.append(n)
    return factors

n = int(input())
if n > 1:
    for factor in prime_factorization(n):
        print(factor)
  • $n$을 소인수분해하기 위해 소수 리스트를 생성하지 않고, 단순히 $i=2$부터 $\sqrt{n}$까지 나눗셈을 통해 소인수를 찾습니다.

 

 

 

✨ 새로 알게 된 점

1. 소수 리스트 생성 방식과 직접 탐색 방식의 비교

소수 리스트를 생성하여 소인수분해를 수행하면, $\sqrt{n}$ 이하의 소수만 검사하면 되기 때문에 불필요한 연산을 줄이고 효율적으로 동작합니다. 특히, 여러 입력에 대해 반복적으로 소인수분해를 수행해야 하는 경우, 소수 리스트를 재사용할 수 있어 성능 면에서 큰 이점을 가집니다. 

반면, 직접 탐색 방식은 소수 리스트를 생성하지 않고 하나씩 나누어보는 방식으로 메모리를 절약하고 구현이 간단합니다. 하지만 소수 여부를 매번 확인해야 하므로 $n$이 크거나 반복적인 작업이 필요할 경우 성능이 떨어질 수 있습니다.

입력 범위 $n \leq 10,000,000$에서는 두 방식 모두 시간 내에 실행 가능하지만, 여러 입력에 대해 반복적으로 처리해야 하는 상황에서는 소수 리스트를 생성하는 방식이 더욱 효율적입니다. 이는 문제의 특성과 입력 형태에 따라 적합한 알고리즘을 선택하는 것이 중요하다는 점을 알게 되었습니다.

 

 

 

반응형

티스토리툴바