파이썬 약수 구하기

1. 설명

• 어떤수의 약수를 구하면 N=A*B 형태로 나타낼 수 있다.
• 하나의 약수, 예를들어 A를 구하면 B는 N/A로 구할 수 있다
• A와 B가 값이 다르다면 2개를 세어주어야 하고, A와 B가 같다면 1개만 세어주어야 한다
• 작은숫자부터 약수 A를 구한뒤 A*A가 N(N은 A*B)보다 작다면, A와 B는 다른값이므로 2개를 세어준다.
  여기서 B는 A보다 큰값을 가지게 된다.
• 만약 A를 구하고, A*A가 N이라면 A와 B는 같은 값이다. 이후 A보다 큰값에서 약수 계산은 이미 계산되어있으므로 불필요하다 
• 이때 시간복잡도는 루트N이다

 

 

 

def divisor(x):
    i = 1
    result = 0
    while i*i<=x:
        if x%i == 0:
            result +=1
            if i*i < x:
                result +=1
        i+=1
    return result

 

혹은

def divisor(x):
    result = 0
    for i in range(1,x+1):
        if x%i == 0:
            result +=1
            if i*i < x:
                result +=1
            else:
                break
    return result

 

 

 

 

2. 약수의 형태는 모르고 특정범위의 약수들의 개수만 구하고 싶을 때

아랫놈이 윗놈보다 더 빠르다

divisor = [1] * 1000001
for i in range(2, e+1):
    for j in range(i,e+1,i):
        divisor[j]+=1