파이썬 약수 구하기

약수를 구하는 방법 1. 

n의 약수를 구하는 상황이라면 1부터 n보다 작거나 같은 수로 n을 나눈다.

나누어 떨어진다면 이는 n의 약수에 해당하게 된다.

ex) 24 -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

n = int(input())
divisor_list = []

for i in range(1, n+1):
	if n % i == 0:
    	divisor_list.append(i)

 

단점 : 이러면 n이 큰 수라면 시간 복잡도가 높아진다. O(N)

 

약수를 구하는 방법(시간 복잡도 단축) 2. 

#코드 Tab 에러가 있음..;;;

n = int(input())

diviors_list = []

for i in range(1, int(n ** (1/2))+1):
	if (n % i == 0):
    	diviors_list.append(i)
        if (i ** 2) != n:
        	diviors_list.append(n//i)

 

1. n의 제곱근(n ** (1/2)) 만큼만 for문을 돌려서 1부터 (n ** (1/2))까지의 수가 i에 들어가도록 한다.

2. n을 i로 나눴을 때, 나누어 떨어질 경우에 약수를 저장하는 리스트에 추가한다.

ex) 24 -> 1, 2, 3, 4, 5,6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 가 약수라면 24의 제곱근 약 5.xx 이하의 수 1, 2, 3, 4, 5 만 n으로 나누어 떨어지는지 확인한다.

3. n의 제곱근 이하의 수(i) 중에서 나누어 떨어지는 수(i)는 약수가 되고, 자연스레 약수는 짝을 이루니까 n을 i로 나누면 짝을 이루는 수를 찾을 수 있다.(24를 예를들면 2같은 경우는 24를 2로 나눈 수는 12 즉, 2의 짝이 되는 수는 12이다.)

4. 참고로 9, 25같은 경우에는 짝이 되는 수가 없으니 그런 수를 제외하고 리스트에 넣어줘야해서 if (i ** 2) != n:으로 필터를 넣어준다.