약수(Divisor)와 소수(Prime number)

약수(Divisor)

• 어떤 수를 나누어 떨어지게 하는 수

예시) 12의 약수는 1, 2, 3, 4, 6, 12이며, 15의 약수는 1, 3, 5, 15입니다.

# 약수 구하기

num = int(input("숫자를 입력하세요: "))

print(f"{num}의 약수: ", end="")

for i in range(1, num+1):
    if num % i == 0:
        print(i, end=" ")

---

소수(Prime number)

• 1과 자기 자신만을 약수로 갖는 수

예를 들어, 2, 3, 5, 7, 11, 13, 17 등은 소수이다. 소수를 판별하는 가장 간단한 방법은 해당 수의 제곱근까지의 수로 나누어 보는 것이다. 만약 약수가 존재한다면 그 약수는 반드시 제곱근을 기준으로 대칭적으로 존재하게 된다. 따라서, 제곱근까지의 수만 확인해보면 된다.

어떤 수 n이 소수인지 여부를 확인하는 가장 간단한 방법

2부터 n의 제곱근까지 모든 수로 n을 나누어 보는 것. 만약 2부터 n의 제곱근까지의 모든 수로 나누어 떨어지지 않으면 그 수는 소수이다. 이를 "소수 판별법"이라고 한다.

예를 들어, 17이 소수인지 판별하려면, 2부터 4까지 17을 나누어 보면 나머지가 0이 아닌 것을 알 수 있으므로 17은 소수이다.

반면, 18은 소수가 아니다. 2부터 4까지 18을 나누어 보면 2로 나누어 떨어지므로 18은 소수가 아니다.

하지만 이 방법은 n이 매우 커질 경우에는 계산량이 많아져서 비효율적이다. 이를 보완하기 위해서는 다른 방법을 사용해야 한다.

소수인지 확인하는 또 다른 방법은 에라토스테네스의 체(에라토스테네스의 채)를 사용하는 것이다.

에라토스테네스의 체는 2부터 차례로 소수를 찾아내는 방법이다. 먼저 2는 소수이므로 2의 배수인 수를 모두 지워준다. 다음으로 3은 소수이므로 3의 배수인 수를 모두 지워준다. 이렇게 반복하여 지워지지 않은 수가 소수이다.

이 방법은 전체 수의 범위가 클 때 효율적이다. 예를 들어 1~1000까지의 소수를 찾을 때는 에라토스테네스의 체를 사용하여 한 번에 찾아낼 수 있다.

# 소수 구하기

n = int(input("정수 n을 입력하세요: "))

for i in range(2, n+1):
    is_prime = True
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            is_prime = False
            break
    if is_prime:
        print(i)