题解归档 - cf755A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755A
• 本地来源：problems/cf755A/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/A
• 原始标题：755A PolandBall and Hypothesis

思路

755A PolandBall and Hypothesis

题意

给定 (n\in[1,1000])，找 (m\in[1,1000]) 使得 (n\cdot m+1) 不是质数。保证答案存在。

思路

• (n) 为奇数时 (m=1)：(n+1) 为大于 2 的偶数，必合数。
• 否则从 (m=1) 起枚举，试除判质数，首个使 (n\cdot m+1) 合数的 (m) 即答案（数据保证 (10^3) 内必有）。

结论

样例：(n=3\to m=1)（得 4）；(n=4\to m=2)（得 9）。

代码

来源：problems/cf755A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:54:09
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll pd(ll x){
    if(x<2) return 0;
    for(lli=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return 1;
}
int main(){
    ll n,i;
    cin>>n;
    for(i=1;i<=1000;i++){
        if(!pd(n*i+1)){
            cout<<i<<"\n";
            break;
        }
    }
    return 0;
}