Kiểm tra số nằm giữa hai số nguyên tố (sandwiched prime) trong C++

Số n được gọi là "sandwiched between primes" nếu n-1 và n+1 đều là số nguyên tố. Ví dụ 642: 641 và 643 đều nguyên tố → 642 sandwiched.

Kiểm tra: hàm isPrime(n) kiểm tra ước số đến √n. Kiểm tra isPrime(n-1) && isPrime(n+1).

Ví dụ

#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*i<=n; i++)
        if (n%i == 0) return false;
    return true;
}

bool isSanwichedPrime(int n){
    return isPrime(n - 1) && isPrime(n + 1);
}

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";
    }
}

Kết quả

642 is Sandwiched between primes: 641 and 643