문제
두 정수 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의 제곱근을 넣어 해당 범위까지의 값을 구하고, 나누었다.
이렇게 진행을 하니 약수 구하기 시간초과 해결 !!!
