C++로 특정 숫자가 두 소수 사이에 있는지 확인하는 방법

이 글에서는 어떤 숫자가 두 소수 사이에 '끼워져(sandwiched) 있는지' 판별하는 방법을 알아봅니다. 어떤 수 n이 소수 사이에 끼워져 있다는 것은, n 바로 아래의 수(n-1)와 n 바로 위의 수(n+1)가 모두 소수일 때를 의미합니다.

해결 접근 방식

판별 로직은 매우 간단합니다. 주어진 수 n에 대해 다음 두 가지만 확인하면 됩니다.

n - 1이 소수인지 검사하고, n + 1이 소수인지 검사합니다. 두 조건이 모두 참이라면 해당 숫자는 두 소수 사이에 끼워져 있는 것입니다. 소수 판별은 2부터 n/2까지의 수로 나누어 나머지가 0이 되는 경우가 없는지 확인하는 전통적인 방법을 사용합니다.

예제 코드

#include <iostream>
#include <set>
#define N 100005
using namespace std;
bool isPrime(int n) {
   if (n == 0 || n == 1)
      return false;
   for (int i=2;i<=n/2;i++)
      if (n%i == 0)
         return false;
   return true;
}
bool isSanwichedPrime(int n){
   if(isPrime(n - 1) && isPrime(n + 1))
      return true;
   return false;
}
int main() {
   int n = 642;
   if(isSanwichedPrime(n)){
      cout << n << " is Sandwiched between primes: " << n-1 <<" and " << n+1;
   } else {
      cout << n << " is not Sandwiched between primes";
   }
}

코드 설명

isPrime 함수: 입력받은 수가 0 또는 1이면 소수가 아니므로 false를 반환합니다. 이후 2부터 n/2까지 반복하며 나누어 떨어지는 수가 하나라도 있으면 소수가 아니라고 판단합니다. 모든 검사를 통과하면 true를 반환합니다.

isSanwichedPrime 함수: n-1과 n+1이 각각 소수인지 isPrime 함수로 확인한 뒤, 둘 다 소수라면 true를 반환합니다.

main 함수: 예시 값으로 642를 사용합니다. 641과 643은 모두 소수이므로, 642는 두 소수 사이에 끼워져 있는 수입니다.

실행 결과

642 is Sandwiched between primes: 641 and 643

참고: 성능 개선

위 코드의 소수 판별은 시간 복잡도가 O(n)입니다. 더 큰 수를 다룰 경우, 제곱근까지만 검사하면 O(√n)으로 최적화할 수 있습니다. 즉, 반복문을 i <= sqrt(n)까지로 변경하면 됩니다. 또한 여러 개의 수를 반복적으로 판별해야 한다면 에라토스테네스의 체를 사용해 미리 소수 테이블을 만들어 두는 것이 효율적입니다.