약수 - 백준 1037 [Python]

C가 A의 약수라면, A/C도 A의 약수가 되어야 한다. 또 C가 A/C인 경우도 있는데, 이때는 A = C^2이라는 수식이 성립하는 경우이다.

 

따라서 약수를 구할때, 루트 A를 까지 구한 다음, 모든 약수를 구하여 시간복잡도를 줄일 수 있다. 왜냐하면, A만큼 나누어 보는 것이 아니라, 루트 A까지 약수를 구하기 때문에 O(N) > O(루트N)이 되기 때문이다.

 

Example 1)

https://www.acmicpc.net/problem/1037

1037번: 약수

문제 해결)

N의 진짜 약수의 최소와 최대를 곱하면 항상 N이 나오게 된다.

 

정답)

n = int(input())
a = list(map(int,input().split()))
print(min(a)*max(a))