소수 판별

소수: 약수가 1과 자기 자신뿐인 자연수

약수 판별

def is_divisor(n: int, m: int):  # m은 n의 약수인지 판단
    if n % m == 0:  # n을 m으로 나눈 나머지 값이 0이면
        return True
    else:
        return False

소수 판별

import math

def is_prime(num: int):  # num은 소수인지 판단
    count = 1
    if num == 1:  # 1의 경우 소수가 아니므로 바로 False 반환
        return False

    # 루트 num이하 까지만 순회한다.
    for i in range(2, int(math.sqrt(num))+1):  # 루트값이 소수이면 안되므로 int로 형변환
        count += is_divisor(num,i)  # is_divisor가 True일 시 1이 더해짐

        if count >=2:  # count가 2이상이 되면 소수가 아니므로 반복 탈출
            break

    if count == 1:
        return True
    else:
        return False

num의 제곱근 까지만 반복하는 이유

약수는 항상 짝을 갖는다.
Ex) 12의 약수 = 1 x 12, 2 x 6, 3 x 4

즉, 1, 2, 3만 알면 그 뒤의 12, 6, 4는 자동으로 구해진다.
+) sqrt(12) = 3.xxx 이므로 3까지 구할 수 있다. (제곱근을 취하는 이유!)