반응형 파이썬 약수1 파이썬 약수 구하기 1. 설명 어떤수의 약수를 구하면 N=A*B 형태로 나타낼 수 있다. 하나의 약수, 예를들어 A를 구하면 B는 N/A로 구할 수 있다 A와 B가 값이 다르다면 2개를 세어주어야 하고, A와 B가 같다면 1개만 세어주어야 한다 작은숫자부터 약수 A를 구한뒤 A*A가 N(N은 A*B)보다 작다면, A와 B는 다른값이므로 2개를 세어준다. 여기서 B는 A보다 큰값을 가지게 된다. 만약 A를 구하고, A*A가 N이라면 A와 B는 같은 값이다. 이후 A보다 큰값에서 약수 계산은 이미 계산되어있으므로 불필요하다 이때 시간복잡도는 루트N이다 def divisor(x): i = 1 result = 0 while i*i 2022. 12. 13. 이전 1 다음 반응형