약수 찾기

1. Brute force

약수: N을 나누어 떨어지게 만드는 수

n = 100

nums = []

for i in range(1,n+1):
    if n % i == 0:
        nums.append(i)

2. 효울적인 방법

1부터 N까지 찾는게 아니라
N의 제곱근까지만 찾는다.
그리고 1~ N의 제곱근사이에 존재하는 약수가 N을 나눈 몫도 약수이다.

from math import sqrt,floor
n = 100

nums = []

for i in range(1,floor(sqrt(n))+1):
    if n % i == 0:
        nums.append(i)
        if (n/i) !=  i:
            nums.append(n/i)
            

3. 효율적인 소수판별

1과 자신을 제외한 약수가 없는 수를 소수라고 한다.
어떤 수 N이 약수를 가지는지 확인해보면 되는데
앞서 효율적인 약수 판별법에의해 2~ N의 제곱근까지만 약수가 존재하는지 확인해보면 된다.

def is_prime_number(x):

    for i in range(2,floor(sqrt(x))+1):
        if x % i == 0:
            return False

    return True

            

참고
1. https://kbw1101.tistory.com/32
2. https://freedeveloper.tistory.com/391