소수(prime number)란 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수를 말합니다. 예를 들어 2, 3, 5, 7, 11 등이 소수입니다. 반면, 1과 자기 자신 외에 다른 약수를 가지는 1보다 큰 자연수를 합성수(composite number)라고 합니다. 예를 들어 4, 6, 8, 9, 10 등이 합성수입니다. 1은 소수도 합성수도 아닌 특별한 수입니다.
소수 판별의 기본 원리
어떤 수가 소수인지 아닌지를 판별하는 가장 기본적인 방법은 그 수를 나누어보는 것입니다. 특정 수 N이 소수인지 확인하려면, 2부터 시작하여 N-1까지의 모든 자연수로 N을 나누어보는 것입니다. 만약 이 과정에서 나누어떨어지는 수가 하나라도 있다면, N은 합성수입니다. 만약 나누어떨어지는 수가 하나도 없다면, N은 소수입니다.
예를 들어, 7이 소수인지 확인해 봅시다. 2부터 6까지의 수로 7을 나누어보면, 7 ÷ 2 = 3 나머지 1, 7 ÷ 3 = 2 나머지 1, 7 ÷ 4 = 1 나머지 3, 7 ÷ 5 = 1 나머지 2, 7 ÷ 6 = 1 나머지 1 입니다. 나누어떨어지는 수가 없으므로 7은 소수입니다.
효율적인 소수 판별법: 제곱근 활용
위의 방법은 수가 커질수록 매우 비효율적입니다. 다행히 소수를 판별하는 더 효율적인 방법이 있습니다. 바로 '제곱근'을 활용하는 것입니다. 어떤 수 N을 판별할 때, 2부터 N-1까지 모두 나누어볼 필요 없이, 2부터 √N (N의 제곱근)까지만 나누어보면 됩니다. 왜냐하면 만약 N이 합성수라면, N의 약수 중에는 반드시 √N보다 작거나 같은 약수가 존재하기 때문입니다.
예를 들어, 36이라는 수를 생각해 봅시다. √36 = 6입니다. 36을 2부터 6까지만 나누어보면, 36 ÷ 2 = 18, 36 ÷ 3 = 12, 36 ÷ 4 = 9, 36 ÷ 6 = 6 입니다. 이렇게 나누어떨어지는 수가 있으므로 36은 합성수입니다.
만약 13이 소수인지 확인하고 싶다면, √13은 약 3.6입니다. 따라서 2와 3으로만 나누어보면 됩니다. 13 ÷ 2 = 6 나머지 1, 13 ÷ 3 = 4 나머지 1 입니다. 나누어떨어지는 수가 없으므로 13은 소수입니다.
더 빠른 방법: 에라토스테네스의 체
많은 수 중에서 소수를 효율적으로 찾아내고 싶을 때 사용하는 방법이 '에라토스테네스의 체'입니다. 이 방법은 다음과 같습니다.
- 찾고자 하는 범위의 모든 자연수를 나열합니다. (예: 1부터 100까지)
- 2는 소수이므로 남겨두고, 2의 배수들을 모두 지웁니다.
- 다음에 남은 수인 3은 소수이므로 남겨두고, 3의 배수들을 모두 지웁니다.
- 이 과정을 반복하여, 각 단계에서 가장 작은 수를 소수로 남겨두고 그 수의 배수들을 모두 지워나갑니다.
- 이 과정을 √N (범위의 최대값)까지만 반복하면, 남은 수들이 모두 소수가 됩니다.
이 방법은 특정 범위 내의 소수를 한꺼번에 찾아낼 때 매우 유용합니다. 예를 들어, 1부터 30까지의 소수를 찾는다면, √30은 약 5.4이므로 5까지만 반복하면 됩니다.
주의할 점
- 1은 소수가 아닙니다.
- 2는 유일한 짝수 소수입니다.
- 어떤 수가 소수인지 판별할 때는, 2부터 시작하여 해당 수의 제곱근까지만 나누어보면 됩니다.
이러한 방법들을 통해 우리는 어떤 수가 소수인지 아닌지를 효율적으로 구별할 수 있습니다.