Giả thuyết của Henry

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Henry là một cậu bé thông minh từ nhỏ , lớn lên với mong ước tìm ra một thứ gì đó nhằm mang lại vinh quang cho nước nhà ! Một hôm, anh ta nằm mơ một giả thuyết như sau: "Luôn luôn có một số \(n\) mà với mọi số nguyên dương \(m\), \(n \times m + 1\) là số nguyên tố".

Sáng hôm sau, anh ta đem giả thuyết này nói với cuom1999 - vốn là người nối tiếng trong giới coder. Sau một thời gian dài đàm đạo với cuom1999, Henry chợt vỡ mộng khi nghe cuom1999 nói :" Đó là một giả thuyết sai !"

Henry rất tức tối và muốn nhờ bạn giúp anh ấy một chuyện đó là hãy tìm phản ví dụ để chứng minh rằng giả thuyết đó bị sai !

Input

Một dòng duy nhất chứa số nguyên dương \(n (1 \leq n \leq 1000)\).

Output

In ra một số nguyên dương \(m\), sao cho \(n \times m+1\) không phải là số nguyên tố. Chú ý rằng: \(m\) chỉ được cho phép thuộc phạm vi [1,1000]. Nếu có nhiều đáp án thỏa mãn, in ra một đáp án bất kì !

Example

Test 1

Input

Output

Bình luận

#include <bits/stdc++.h>
using namespace std;
int n;
bool snt(int n)
{
    if(n<2)return 0;
    if(n<4)return 1;
    if(n%2==0||n%3==0)return 0;
    if(n==5||n==7||n==11||n==13||n==17||n==19||n==23)return 1;
    if(n%5==0||n%7==0||n%11==0||n%13==0||n%17==0||n%19==0||n%23==0)return 0;
    for(int i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return 0;
    }
    return 1;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    cin >> n;
    for(int i=2;i<=1000;i++)
    {
        if(!snt(n*i+1))
        {
            cout << i;
            break;
        }
    }
    return 0;
}

4 bình luận nữa