[Python 꿀팁] 많은 수의 약수를 구할 때

일반적으로 약수를 구하는 방식을 생각해보면 0부터 해당 수까지 모두 나누어보며 나머지가 0인 수의 개수를 더하는 방식이 떠오르는데 코드로는 아래와 같다.

def yaksu(num):
	answer = 0
	for i in range(1,num+1):
    	if num%i == 0:
        	answer += 1
	return answer

 

한 수의 약수만을 구할 때에는 정석적인 풀이지만

만약 1부터 100000까지 약수의 합을 구한다면 아래와 같은 시간이 소모된다

from tqdm import tqdm
from time import time

start = time()
result = 0
for i in tqdm(range(1,100001)):
    result += yaksu(i)
end = time()

print(f'The answer is {result}\n spending time is {round(end-start, 2)}sec')

3분 28초가 소모되었다.

 

만약 계산 과정에서 i는 i, i*2, i*3...의 약수임을 이용하여

각 배수의 위치에 약수의 수를 더하면 loop 횟수를 획기적으로 줄일 수 있다.

 

코드로는 아래와 같다.

from tqdm import tqdm
from time import time

start = time()

number = 100000
l = [0 for i in range(number)]
for i in tqdm(range(number)):
    for j in range(1, number // (i + 1) + 1):
        l[(i + 1) * j - 1] += 1
result = sum(l)

end = time()

print(f'The answer is {result}\n spending time is {round(end-start, 2)}sec')

코드를 수정한 후 소요시간이

3분 28초 > 0.2초로 줄어들어 압도적인 성능 차이를 보여준다.