Tìm m để bác bỏ giả thuyết số nguyên tố bằng C++

Mô tả bài toán

Giả thuyết: tồn tại n dương sao cho với mọi m dương, n*m+1 là số nguyên tố. Tìm m làm ví dụ ngược (n*m+1 không nguyên tố).

Ví dụ

n=12 → m=10 vì 12*10+1=121=11^2 không nguyên tố.

Thuật toán

Nếu n<3 → m=n+2 (vì n=1: 1*3+1=4; n=2: 2*4+1=9). Nếu n≥3 → m=n-2 (vì n*(n-2)+1 = n^2-2n+1 = (n-1)^2 hợp số).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    if (n < 3) return n + 2;
    else return n - 2;
}

int main() {
    int n = 12;
    cout << solve(n) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 12

Output: 10