이번 문제는 주어진 숫자에서 Prime factor를 찾아 그 중에서 가장 높은 수를 답하는 문제입니다. 그렇다면 Prime factor를 알아야 하는데... Prime이란 바로 '소수' 입니다. '소수'라 함은 1과 자신을 제외한 나머지로 나눠지는 수가 없는 수를 말합니다.
그럼 결론은 소인수분해를 해서 그 중에서 가장 큰 수를 찾으면 된다는 말이네요... 하지만 주어진 입력값은 600851475143 입니다. 결코 적은 수가 아닙니다... 1e9 정도가 1초걸리는 연산이라고 가정할때, 무려 600초 이상이 걸리는 큰 수입니다... 프로그램을 돌리고 결과를 기다릴때까지 10분이나 기다려야 한다면 정말 안타까운 일이 아닐 수 없습니다.
그럼 여러가지 시간을 단축시킬 방법을 생각해야 합니다. 제가 생각한 방안은 다음과 같습니다.
- 1부터 입력값까지 하나하나 찾으면서 소수인지 아닌지를 찾을필요없이, 제곱근(sqrt)을 구해서 거기 까지만 찾아간다. 왜냐하면, 제곱근을 넘어서는 수는 이미 앞에서 계산한 수의 반대편 쌍이되기 때문입니다.
- 찾는값을 최초에 입력값으로 시작해서, 계산할때마다 줄여나간다. 왜냐하면, 이미 작은수의 소인수로 나눠지면 그 반대값은 가장큰 소수의 대상이 될 수 있기 때문입니다. 그 수는 계속 연산을 반복하면서 작아지겠죠??
이걸 조합해서 구현해보면 아래와 같습니다.
import math
import time
def calcPrimeFactor(input):
sqrtRes = int(math.sqrt(input))
target = input
i = 2
while i <= sqrtRes :
a, b = divmod(target, i)
if (b == 0) :
target = a
i = 2
sqrtRes = int(math.sqrt(target))
continue
else :
i += 1
return target
if __name__ == '__main__' :
start = time.time()
ans = calcPrimeFactor(600851475143)
print(ans)
print("Working Time : ", time.time() - start)다행히 통과했고... 동작시간은 Working Time : 0.0047910213470458984 정도가 걸렸습니다.
그렇다면... Test_Case가 주어지고 case만큼 입력값이 있어서 계산 후 출력을 해야한다면 어떻게 될까요?? 살짝 코드만 변경해 보도록 하겠습니다. 원체 걸린 시간이 길지 않아서 따로 로직에 대한 걱정은 할 필요가 없을 것 같습니다.
import math
def calcPrimeFactor(input):
sqrtRes = int(math.sqrt(input))
target = input
i = 2
while i <= sqrtRes :
a, b = divmod(target, i)
if (b == 0) :
target = a
i = 2
sqrtRes = int(math.sqrt(target))
continue
else :
i += 1
return target
if __name__ == '__main__' :
tc = int(input())
for i in range(tc) :
targetNo = int(input())
print(calcPrimeFactor(targetNo))이렇게 level이 3이 되었습니다.
-Ayotera Lab-
댓글