소수(素數)란 1과 자기 자신, 딱 두 개의 수로만 나누어 떨어지는 수를 말합니다. 여기서 어떤 수의 '약수'란 그 수를 나누어 떨어지게 만드는 수를 의미합니다.
가장 작은 열 개의 소수는 다음과 같습니다.
2, 3, 5, 7, 11, 13, 17, 23, 29, 31
소수가 아닌 수를 합성수라고 부릅니다. 합성수는 세 개 이상의 약수를 가진 수입니다. 그리고 1은 자기 자신으로만 나누어 떨어지기 때문에 소수도 합성수도 아닌 특별한 수입니다.
소수 판별 조건
어떤 수가 소수인지 확인하려면 다음 두 가지 조건을 모두 만족해야 합니다.
- 1보다 큰 자연수여야 합니다.
- 약수가 1과 자기 자신, 단 두 개뿐이어야 합니다.
이 두 조건을 모두 충족하면 그 수를 소수라고 할 수 있습니다.
소수 판별 알고리즘
프로그램에서는 주어진 수를 그보다 작은 수들로 하나씩 나누어 보는 방식으로 소수 여부를 검사합니다. 검사 도중 단 하나라도 나누어 떨어지는 수가 발견되면 그 수는 소수가 아니며, 끝까지 나누어 떨어지는 수가 없다면 소수입니다.
두 개의 숫자를 예로 들어 이 과정을 직접 살펴보겠습니다.
예제 1: 42는 소수인가?
입력 − Number1 − 42 출력 − 42는 소수가 아닙니다
검사 과정: 1보다 크고 42보다 작은 모든 수로 42를 나누어 봅니다.
42 ÷ 2 = 21, 즉 42는 2로 나누어 떨어집니다. 따라서 42는 1과 자기 자신 외의 다른 수로도 나누어 떨어지므로 소수가 아닙니다.
예제 2: 7은 소수인가?
입력 − Number2 − 7 출력 − 7은 소수입니다
검사 과정: 1보다 크고 7보다 작은 모든 수로 7을 나누어 봅니다.
- 7은 2로 나누어 떨어지지 않으므로 다음 수인 3을 검사합니다.
- 7은 3으로 나누어 떨어지지 않으므로 다음 수인 4를 검사합니다.
- 7은 4로 나누어 떨어지지 않으므로 다음 수인 5를 검사합니다.
- 7은 5로 나누어 떨어지지 않으므로 다음 수인 6을 검사합니다.
- 7은 6으로도 나누어 떨어지지 않습니다. 즉, 7은 1과 7로만 나누어 떨어지므로 소수입니다.
반복 횟수 줄이기 – 최적화된 방법
위 로직을 그대로 사용하면 숫자가 1,000이나 100,000처럼 커질 때 for 루프가 그만큼 많은 반복을 수행해야 하므로 연산 시간이 크게 늘어납니다.
이를 개선하려면 루프를 절반까지만 실행하면 됩니다. 예를 들어 숫자가 77이라면 루프는 38까지만 돌리면 됩니다. 어떤 수 n의 약수 중 n/2보다 큰 값은 n 자신뿐이기 때문입니다. 이렇게 하면 필요한 반복 횟수를 절반으로 줄일 수 있고, 실제로는 √n까지만 검사해도 충분하므로 더욱 효율적인 구현도 가능합니다.
C 코드 예제
#include <stdio.h>
int main() {
int num = 33, flag = 0;
for(int i = 2; i <= num / 2; i++) {
if(num % i == 0) {
printf("%d은(는) 소수가 아닙니다", num);
flag = 1;
break;
}
}
if(flag == 0) {
printf("%d은(는) 소수입니다", num);
}
return 0;
}
실행 결과
33은(는) 소수가 아닙니다
33은 3 × 11로 나누어 떨어지므로 소수가 아니라 합성수입니다. 위 코드는 33을 2부터 16(num/2)까지의 수로 차례대로 나누어 보다가, 3으로 나누어 떨어지는 순간 "소수가 아니다"라는 메시지를 출력하고 break 문으로 반복을 종료합니다.
여기서 flag 변수는 소수 여부를 기록하는 역할을 합니다. 반복문 안에서 약수가 발견되면 flag가 1로 설정되고, 반복문이 끝난 후 flag가 여전히 0이라면 나누어 떨어지는 수가 없었다는 뜻이므로 해당 수를 소수로 판별해 출력합니다.