숫자 n이 주어졌을 때, n보다 작은 수 중에서 가장 가까운 소수를 찾아야 합니다. 이 문제는 n - 1부터 차례대로 검사를 시작하면 아주 간단하게 해결할 수 있습니다. 예시를 통해 살펴보겠습니다.
입력
10
출력
7
알고리즘
- 숫자 n을 초기화합니다.
- n - 1부터 1까지 반복하는 루프를 작성합니다.
- 발견된 첫 번째 소수를 즉시 반환합니다.
- 주어진 n보다 작은 소수를 찾지 못했다면 -1을 반환합니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
if (n == 2) {
return true;
}
for (int i = 2; i <= ceil(sqrt(n)); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int getNearestPrimeNumber(int n) {
for (int i = n - 1; i > 1; i--) {
if (isPrime(i)) {
return i;
}
}
return -1;
}
int main() {
int n = 20;
cout << getNearestPrimeNumber(n) << endl;
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
19
코드 설명
isPrime 함수는 2부터 √n까지의 수로 나누어 떨어지는지 확인함으로써 해당 숫자가 소수인지 판별합니다. 나누어 떨어지는 수가 없으면 소수로 판단하고 true를 반환합니다.
getNearestPrimeNumber 함수는 n - 1부터 시작해 2까지 내려가면서 각 숫자에 대해 소수 여부를 검사하고, 가장 먼저 발견되는 소수를 반환합니다. n이 20일 경우 19가 소수이므로 바로 19가 출력됩니다.