이 튜토리얼에서는 C++을 사용하여 주어진 두 정수 사이에 존재하는 소수(prime number)를 찾는 프로그램을 만드는 방법을 알아보겠습니다.
프로그램은 시작 값(하한)과 끝 값(상한)으로 두 개의 정수를 제공받으며, 우리의 목표는 해당 범위 안에 포함된 모든 소수를 찾아 출력하는 것입니다.
동작 원리
소수를 판별하는 기본 아이디어는 다음과 같습니다.
- 0과 1은 소수가 아니므로 검사 대상에서 제외합니다.
- 각 숫자 i에 대해 2부터 i/2까지의 수로 차례대로 나누어 보고, 나누어 떨어지는 경우(약수가 존재하는 경우) 소수가 아니라고 판단합니다.
- 중간에 나누어 떨어지는 수가 하나도 없다면 그 숫자는 소수입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, i, j, flag;
// 하한 범위 설정
a = 3;
// 상한 범위 설정
b = 12;
cout << "\nPrime numbers between "
<< a << " and " << b << " are: ";
for (i = a; i <= b; i++) {
if (i == 1 || i == 0)
continue;
flag = 1;
for (j = 2; j <= i / 2; ++j) {
if (i % j == 0) {
flag = 0;
break;
}
}
if (flag == 1)
cout << i << " ";
}
return 0;
}
실행 결과
Prime numbers between 3 and 12 are: 3 5 7 11
코드 설명
먼저 변수 a와 b에 각각 탐색 범위의 하한값인 3과 상한값인 12를 저장합니다. 이후 for 반복문을 통해 a부터 b까지의 모든 숫자를 하나씩 검사합니다.
내부 반복문에서는 현재 숫자 i를 2부터 i/2까지의 값으로 나누어 나머지가 0이 되는지 확인합니다. 나누어 떨어지면 약수가 존재한다는 의미이므로 flag를 0으로 설정하고 더 이상 검사하지 않고 반복문을 빠져나옵니다.
모든 검사를 통과하여 flag가 여전히 1이라면 해당 숫자는 소수이므로 화면에 출력합니다.
성능 개선 팁
위 코드에서는 내부 반복문의 조건을 j <= i / 2로 설정했지만, 실제로는 어떤 수의 약수 중 가장 큰 것은 그 수의 제곱근(√i)을 넘지 않으므로 j * j <= i 또는 j <= sqrt(i) 조건으로 바꾸면 검사 횟수를 크게 줄여 성능을 향상시킬 수 있습니다.