[파이썬] 약수 찾기 알고리즘

Contents

문제

내용

• 약수 찾기 문제였는데 아무 생각없이 을 썼더니 제출 전에 제공된 테스트 케이스는 전부 통과했는데, 인풋값이 최대 10만까지 들어갈 수 있는 채점용 테스트 케이스는 10초의 시간 제한을 초과해 버렸다.

• 약수 찾기 자체는 으로 줄일 수 있다고 하여 구글링을 통해 알아보았다.

약수를 쉽게 찾는 방법

1. n의 제곱근을 1~(n의 제곱근)으로 % 연산을 한다.

# 100의 제곱근은 10이므로 10을 1~10까지 % 연산을 하자
10 % 1 = 0
10 % 2 = 0
10 % 3 = 1
10 % 4 = 2
10 % 5 = 0
10 % 6 = 4
10 % 7 = 3
10 % 8 = 2
10 % 9 = 1
10 % 10 = 0

# 100의 제곱근 10을 나누어 떨어지게 하는 수는 1, 2, 5, 10

2. n에, 앞서 구한 n의 제곱근을 나누어 떨어지게 하는 값으로 나눈다.

100 / 1 = 100
100 / 2 = 50
100 / 5 = 20
100 / 10 = 10

# 결과는 10, 20, 50, 100

3. 1번의 결과와 2번의 결과를 합치고, 중복되는 값을 제거한다. 필요시 정렬 연산을 수행하여 마무리한다.

1, 2, 5, 10, 10, 20, 50, 100

# 중복되는 값 제거
1, 2, 5, 10, 20, 50, 100

4. 이로써 100의 약수를 모두 구하였다. 다시 과정을 정리하자면
1. n의 제곱근을 1~(n의 제곱근)으로 나눈다.
2. n을 a에서 구한 값으로 나눈다.
3. a와 b의 결과값들을 하나로 합친다. 이때 중복된 요소는 제거한다. 필요하면 정렬 연산을 수행한다.

• 파이썬 예시

from math import sqrt

def find_divisor(n):
    result = []

    temp = []
    temp2 = []
    
	# 1) n의 제곱근을 1~(n의 제곱근)으로 나눈 것 중 나누어 떨어지게 하는 나누는 수를 추가한다.
    for i in range(1, int(sqrt(n))+1):
      if n % i == 0:
        temp.append(i)
    
	# 2) n을 a에서 구한 값으로 나눈다.
    for i in temp:
	    temp2.append(int(n / i))
    
	# 3) 요소 중복 제거 및 정렬
    result = list(set(temp + temp2))  
    result.sort()
    
    return result

적용 결과

출처