BOJ 16563번: 어려운 소인수분해

www.acmicpc.net/problem/16563

16563번: 어려운 소인수분해

아이디어:

소수판정법을 이용하여 2부터 루트n 까지 for문을 돌면서 나누어지는 수를 출력하고 계속 반복하는 방식으로 구현했더니 시간초과가 났다.

#시간초과
import sys, math

N = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split()))

def solve(n):
    m = math.floor(n**0.5+1) 
    for i in range(2, m):
        if (n%i!=0): continue
        while (n%i==0):
            print(i, end=" ")
            n//=i
    if (n!=1):
        print(n)
    else: print()

for n in k:
    solve(n)

 

 

그래서 구글링을 해보니 에라토스테네스의 체 를 사용하여 풀더라.. 공간복잡도 안에 들어오면 이 방법이 훨씬 빠른가보다.

일단 에라토스테네스의 체를 이용하여 1~500만까지의 소수를 구한 후에, 구한 소수들로 주어진 입력을 소인수 분해하여 출력하면 된다.. 라고 쉽게 생각했는데 파이썬을 이용하여 구현하는 게 어려웠다.

 

1. 먼저 500만까지의 수가 들어있는 배열을 만든다.

2. 해당 배열 인덱스를 2부터 루트 500만까지 돌면서 소수인 경우 즉, 인덱스와 값이 같을 경우에 해당 수의 배수인덱스를 모두 해당 수로 바꾸어 주었다. 여기서 루트 500만을 **0.5로 구했는데 range안에는 float 값을 넣을 수 없어서 오류가 났었다.ㅎ..

3. 그리고 소인수분해를 하는 함수 solve에서 입력으로 주어진 n을 matrix[n]으로 나누면서 계속 갱신하고 n을 출력하였다.

 

import sys, math

N = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split()))

matrix = [0]*(5000000+1)
for i in range(1,5000000+1):
    matrix[i] = i

for i in range(2, int(5000000**0.5+1)):
    if (matrix[i]==i): #소수인경우
        for j in range(i*i, 5000000+1, i): #배수도 모두 소수로
            if (matrix[j]==j):
                matrix[j]=i

def solve(n):
    while (n>1):
        print(matrix[n], end=" ")
        n //= matrix[n]
    print()

for n in k:
    solve(n)