약수의 개수 구하기 계산 시간

약수의 개수를 구하는 방법은 크게 3가지로 나뉜다. 각 방법들의 실행 시간은 서로 유의미한 차이를 가진다.

1부터 num까지의 약수를 구하는 방법

방법1
: 1부터 num까지 전부 다 나눠가며 나머지가 0이면 카운트+=1. 코드는 생략

방법2
: 1부터 절반까지 나눠가며 나머지가 0이면 카운트+=1

def count(num):
	cnt = 0
    for i in range(1, int(num/2)+1):
        if num%i==0: cnt+=1
    return cnt+1
 

방법3
: 제곱근까지 나눠가며 나머지가 0일때 num이 1이거나 나누는 숫자가 num의 제곱근인 경우 카운트+=1, 그외엔 카운트+=2

for i in range(1, int(n**(1/2))+1):
	if n%i==0: 
		if n == 1 or i**2 == n: cnt+=1
		else: cnt+=2 
	return cnt