CodeUp 2055 Python

코드업 2055 파이썬 풀이

두 정수의 약수를 구하는 문제이다. 기존에 약수를 구하던 방식으로 구하려고 했지만(나눠서 나머지가 0이면 추가하는 방식), 그렇게 코드를 짜니 시간 초과가 나왔다. 두 정수의 범위가 1,000,000,000이나 되니 이 루프를 두 번씩이나 반복하면 당연히 시간 초과가 난다고 한다.

 

시간 초과를 해결하기 위해 제곱근을 구하는 math.sqrt()를 사용하기로 했다. 아무리 큰 정수라도 제곱근을 시키면 범위가 확 줄어든다. 그리고 어차피 약수는 제곱근을 해도 구할 수 있다. 예를 들어 100의 약수를 구한다면, 제곱근인 10까지로만 나눠봐도 1*100 2*50 4*25 5*20 10*10으로 약수가 다 나와버린다. 그래서 나는 input을 제곱근 처리한 후, 그 범위까지 for문을 사용하여 나눈 후, 그 값을 약수 리스트에 추가하는 방식을 사용했다.

get_divisors라는 약수 리스트를 만드는 함수를 생성했다. length가 input의 제곱근이고, [8]~[10]에서 본격적으로 약수를 구하고, sort를 사용해서 오름차순으로 정렬했다.

 

그 후에는 a,b에서 중복되는 약수를 제거하기 위해 set를 사용했다.

마지막으로 출력은 리스트의 요소를 뽑아내는 pop을 사용하여 처리하였다.