기사단원의 무기→약수를 구하는 효율적인 알고리즘★★

100의 약수는 아래와 같다.

1, 2, 4, 5, 10, 20, 25, 50, 100.

 

1단계-약수 구하기

통상적(본능적)으로 다음과 같이 구한다. 

def divisor_v1(N):
    result=[]
    for i in range(1, N+1):
        if N % i==0:
            result.append(i)
    return result
    
#N=100인 경우 출력결과는 아래와 같다.
#[1, 2, 4, 5, 10, 20, 25, 50, 100]

 

2단계- 제곱근을 기준으로 약수 구하기

 

"N의 약수를 구할 때는, "1부터 N의 제곱근까지"의 수로 나누어 떨어지는지 확인하면 된다!"

 

 

즉 100의 제곱근인 10을 기준으로 좌측(작은 약수)와 우측(큰 약수)를 각각 구하고,

 

그 다음에 중복되는  요소를 제거해 주면 된다. 

아래에서 100의 약수를 구하는 사례를 살펴보자.

우리는 작은 약수를 구하기 위해서 100제곱근인 10까지만 즉,

 

1 ~ 10 사이의 수에 대해서,

 

100이 0으로 나누어 떨어지는지 보면 된다.

 
100 % 1 = 0

100 % 2 = 0

100 % 3 = 1

100 % 4 = 0

100 % 5 = 0

100 % 6 = 4

100 % 7 = 2

100 % 8 = 4

100 % 9 = 1

100 % 10 = 0

 

이를 통해서, 100의 약수는 일단 1, 2, 4, 5, 10 (작은 약수i)을 갖는다는 것을 알게 되었다.

이제 이 수(작은 약수들)를 가지고, N인 100을 나누어 주자

바로 100에 이미 구해진 1, 2, 4, 5, 10을 나누는 것이다.

 

100 / 1 = 100

100 / 2 = 50

100 / 4 = 25

100 / 5 = 20

100 / 10 = 10

 

그렇게 되면, 이미 구했던 1, 2, 4, 5, 10 외에 100, 50, 25, 20, 10이 추가로 구해진 약수(큰 약수)가 된다는 것을 알 수 있다.

 

why 이렇게 하냐면

N=A * B 이므로

 

앞에서 구한 작은 약수(제곱근을 포함해서 좌측으로 약수)로 N을 나누어 주면

 

제곱근을 기준으로 우측에 있는 큰 약수를 구할 수 있기 때문이다.

이제, 중복을 제거하고 오름차순으로 순서를 정렬하면 된다. 

 

코드로 구현하면 다음과 같다. 

 

from math import sqrt
def divisor_v2(N):
    result=[]
    for i in range(1, int(sqrt(N))+1):
        #제곱근을 포함해서 작은 약수 구하기
        if N % i == 0:
            result.append(i)
          	
            #작은 약수i와 큰 약수 N//i의 중복을 제거하면서, N//i 큰 약수 구하기
            if i != N // i:
                result.append(N // i)
	#오름차순으로 정렬하기                
    result.sort()
    return result
    
#N=100인 경우 출력결과는 아래와 같다.
#[1, 2, 4, 5, 10, 20, 25, 50, 100]

▶ 다만 주의 할 점은 "제곱근"까지 이므로 +1을 해줬으며, 

▶ 작은 약수와 큰 약수의 중복 카운팅을 막기 위해서 i !=N//i 을 사용하였다. 

 

▶ N % i ==0 에서 N=100,  i=10이면  i는 10이고, N//i도 역시 10이다. 

 

▶ 중복을 방지하기 위해  i != N//i  → "작은 약수 != 큰 약수" 가 서로 다를 때

    result리스트에 append하도록 하였다. 

 

▶ N = A * B 일 때,  A == B 일 수 있기 때문에 (ex. 100 = 10 * 10 )  큰 약수와 작은 약수를

    중복해서 넣어주지 않기 위해

    작은 약수 i를 제곱했을 때  N이 않되는지 검사하는 다음과 같은 방법도 있다. 

if i != N // i:
    result.append(N // i)
       ↓ 대체가능
if ( (i**2) != N) :
	result.append(N // i)

 

 

▶ 다음과 같이 중복 제거를 위해 set을 사용하는 방법도 있다. 

from math import sqrt
def divisor_v3(N):
    data = set()

    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
            data.add(i)
            data.add(N // i)
    return sorted(data)

 

 

 

3단계- v2을 이용해서 약수의 개수 구하기 

 

append() 메서드를 지우고, cnt+=1를 추가 하였다.  

from math import sqrt
def divisor_cnt(N):
    cnt=0
    for i in range(1, int(sqrt(N))+1):
         #작은 약수i를 넣는다. 작은 약수들: N의 제곱근을 기준으로 좌측에 있는 부분
        if N % i == 0: 
            cnt+=1
            #큰 약수num//i 를 넣는다.  큰 약수들: N의 제곱근을 기준으로 우측에 있는 부분
            if i != N // i:
                cnt+=1
                
    #약수의 갯수를 반환
    return cnt
    
 #N=100인 경우 약수의 갯수는 9개이다.

 

 

 

4단계 - 약수 갯수 구하기-대칭성이용★★ 

from math import sqrt
def divisor_cnt(n: int) -> int:
    cnt = 0
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            #작은 약수i와 큰 약수n//i가 중복된다. 즉 겹쳐진다. 한번만 카운팅 하자  i=10  n//i=100/10=10
            if n // i == i:
                cnt += 1
            #작은 약수i와 큰 약수n//i가 중복되지 않는다. 작은 약수 1번 카운팅+큰 약수 1번 카운팅 → 총 2번씩 카운팅하자.
            else:
                cnt += 2
    return cnt


number = 5
print(divisor_cnt(number))

▶ if n // i == i: 의미

 

▶ 작은 약수(i)와 큰 약수(n//i)가 겹친다. 1번만 카운팅하자.

 

 

 

 

5단계 -기사단원의 무기→4단계 함수 이용★

from math import sqrt
def divisor_cnt(n, limit, power) -> int:
    cnt = 0
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            #작은 약수i와 큰 약수n//i가 중복된다. 즉 겹쳐진다. 한번만 카운팅 하자  i=10  n//i=100/10=10
            if n // i == i:
                cnt += 1
            #작은 약수i와 큰 약수n//i가 중복되지 않는다. 작은 약수 1번 카운팅+큰 약수 1번 카운팅 → 총 2번씩 카운팅하자.
            else:
                cnt += 2
    #필터링 작업
    if cnt> limit:
        return power
    return cnt


def solution(number, limit, power):
    answer=0
    for i in range(1, number+1):
        divisor_num=divisor_cnt(i, limit, power)
        answer+=divisor_num
    return answer

 

 

 

 

https://kbw1101.tistory.com/32

[알고리즘] 효율적으로 약수를 찾는 알고리즘

일부인용을 밝힙니다.