BOJ_11653_소인수분해

백준 #11653 소인수분해

• 알고리즘 스터디 문제 풀이입니다.
• 백준 11653번 에서 풀어볼 수 있습니다.

문제설명

• 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
• N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

풀이1.

index 2부터 index로 값이 나눠지는지 확인하고 더 이상 나눠지지 않으면 index를 1씩 증가하면서 다시 나눠지는지 확인한다.

def factorization(n):
    index = 2
    while n != 1:
        if n % index == 0:
            print(index)
            n /= index
        else:
            index += 1

N = int(input())

factorization(N)

풀이2.

해당 숫자의 √N 까지 확인하는 방법으로 시간 복잡도를 개선해본다.
예를 들어 N = 129일때, index가 2부터 증가하면서 나눠지는 지 확인한다.
index가 3일 때 값이 나눠지므로 N = 43 이 되고 index는 4부터 1씩 증가하면서 다시 반복한다.
이 때, √129 = 11.XX 이므로 index가 43이 될때까지 확인하지 않고, 12 까지만 확인하여 시간을 줄일 수 있다.

import math

def factorization(n):
    index = 2
    while n != 1:
        if index > math.sqrt(n):
            print(int(n))
            return

        if n % index == 0:
            print(index)
            n /= index
        else:
            index += 1

N = int(input())

factorization(N)

💡

두 번째 풀이에서 n /= index 할때 값이 float로 나오기 때문에 print할 때 정수형으로 변환해야한다.

🎁 관련 문제

• 백준 1978번 소수 찾기
• 백준 1929번 소수 구하기

2, 3, 5, 7, 11 ... 등 1과 자기 자신만을 약수로 갖는 수를 소수라고 한다.
소수를 판별하는 방법 : 2부터 판별값까지 값을 나눠서 나머지가 0이 안나오면 소수로 인정한다

• 소수 판별 알고리즘 풀이

1. 풀이1과 같이 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 안나온다면 소수로 정의한다. 해당 수까지 모두 확인해야하므로 시간복잡도는 O(N) 이 되고, 가장 원초적인 방법이다.
   

2. 두번째는 해당 숫자의 절반까지만 확인하는 방법이다. 절반 이상의 숫자들은 확인이 필요 없는 숫자들이기 때문이다. 예를 들어 80이란 숫자에서 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이되는 숫자는 나올수가 없다. 해당 풀이를 사용하면 최대 N/2번 조회를 한다. 시간복잡도에서 상수는 제외하므로 해당 풀이의 시간복잡도도 O(N) 이 된다.
   

3. 풀이2에서 사용한 방법이다. 해당 숫자의 √N 까지 확인하는 방법으로 원리는 약수의 중심을 구하는 방법이다. 예를 들어 80의 약수는 아래와 같다.
   1, 2, 4, 5, 8, 10, 16, 20, 40, 80 √80의 값은 대략 8.xxx의 값으로, 약수들의 곱으로 봤을 때 중간값이 된다. 이 원리를 이용하여 2에서부터 √N의 값까지 검색을 한 이후의 값은 확인할 필요가 없게 되고 시간복잡도는 O(√N) 이 된다.
   

4. 에라토스테네스의 체 라는 방법을 사용한다.

   1. 1~20까지의 소수를 구한다고 하면, 1 은 소수가 아니니 버린다.

      2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

   2. [2]는 소수이다 -> 2의 배수는 소수가 아니다 -> 지운다

      2	3	5	7	9	11	13	15	17	19

   3. [3]는 소수이다 -> 그러면 3의 배수는 소수가 아니다 -> 지운다

      2	3	5	7	11	13	17	19

   4. [5]소수이다. -> 그러면 5의 배수는 소수가 아니다. -> 지운다.(지워져있다.)

      2	3	5	7	11	13	17	19

   5. 이런식으로 쭉쭉쭉 가면서 이미 정해진 소수의 배수인 것들을 지워서 소수를 구하는 방법이 "에라토스테네스의 체" 방법이다.

   6. 위 4번에서 5의 배수를 지우려는데 10, 15가 이미 지워져있다. (2의 배수, 3의 배수로 이미 지워짐) 중복이 없을때 부터 배수를 지우려면 제곱한 수 부터 배수를 지우면 된다. 5의 배수를 지운다면, 5의 제곱인 25부터 25+ 5, 25+ 2x5, 25+ 3x5 . . 이런식의 배수n^2 + i x n를 지운다. 그러면 그 전에 이미 지워져있는 배수들은 건너 뛸 수 있다.