[python] 약수 구하기

기사단원의 무기 문제를 풀다가 시간 초과가 났다.

약수 구할 때 1 ~ n까지 for문 돌렸더니 시간 초과가 났더랬다 ..

for i in range(1, number+1):
        cnt = 0
        for j in range(1, int(math.sqrt(i))+1):
            if i%j == 0:
                cnt+=1
                if j*j != i:
                    cnt+=1

이런 식으로 기준 숫자의 제곱근까지만 구해도 약수를 구할 수 있다.

중간에

if j*j != i:
     cnt+=1

이걸 하는 이유는 25 = 5 * 5 처럼 똑같은 숫자를 곱하는 경우를 걸러내고,
6 = 2 x 3 = 3 x 2 같은 경우를 세어주는 것이당

약수 구하기 코드를 소수 만들기 문제에도 활용했다! 유용하군