[codeup] 2055. 두 수의 약수 구하기

문제

두 정수 a, b의 약수를 모두 출력하는 프로그램을 작성하시오.

입력

두 정수 a, b가 입력된다. (1 <= a <= b <= 1,000,000,000)

출력

두 정수 a, b의 약수를 오름차순으로 출력한다.

(중복된 약수는 한번만 출력한다.)

입력 예시

6 14

출력 예시

1 2 3 6 7 14

실행 코드

처음 해당 코드를 작성했을때, 테스트로 작성한 입력/출력에 대해 특이사항이 없어 답안을 제출했으나, 시간 초과가 났다.

a,b = map(int,input().split(" "))

def get_divisor(number):
    numbers = []
    for i in range(1,number+1):
        if number % i == 0:
            numbers.append(i)
    return numbers

def delete_duplication(a,b):
    result = []
    result = get_divisor(a) + get_divisor(b)
    result = list(set(result))
    result.sort()       
    return result
    
temp = delete_duplication(a,b)
print(' '.join(map(str,temp)))

시간초과가 나는 거에 대해서는 아마 일일히 조회를 하는 부분으로 인하여 발생을 하는 것으로 추측되는데, 이걸 내가 아는 지식선에서 어떻게 해결할 수 있을까?

약수를 구하는 방법을 여러가지 찾아보던 중, 약수를 더 빠르게 구할 수 있는 방식을 찾았다.

힌트는 "제곱근"

"모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다."

어떤 큰 수를 소인수분해 할때, 그 수의 제곱근 보다 큰 수로 나눌 필요가 없다.
이 부분이 시간을 줄일 수 있는 아주 큰 단서가 되었다.

예를 들어보면 8의 약수를 구한다고 가정했을때,

8 = [ 1, 2, 4, 8 ] 로 표기할 수 있는데, 이를 자세히 보면

i * i 이 8을 초과하게 되려면

1 X 1 = 1
2 X 2 = 4 : 여기까지 계산이 되어야 한다.
3 X 3 = 9

즉, i는 1, 2가 되어 들어가게 되는거고 n/i로 되어 8, 4가 들어가게 된다.
이로서 4개의 약수 구하는 것이 가능해진다.

이를 이용하여 코드에 적용하였다.

import math

a,b = map(int,input().split(" "))

def get_divisor(number):
    num = 0
    num = math.sqrt(number)
    numbers = []
    for i in range(1,int(num)+1):
        if number % i == 0:
            numbers.append(i)
            numbers.append(number//i)
    return numbers

def delete_duplication(a,b):
    result = []
    result = get_divisor(a) + get_divisor(b)
    result = list(set(result))
    result.sort()       
    return result
    
temp = delete_duplication(a,b)
print(' '.join(map(str,temp)))

크게 바뀐 부분은 없고, def get_divisor부분에 num이라는 변수를 추가하고, number의 제곱근을 넣어 해당 범위까지의 값을 구하고, 나누었다.

이렇게 진행을 하니 약수 구하기 시간초과 해결 !!!