CCF NOI1066. 素数对 (C++)_输入一个正整数n(5<=n<=10000), 从小到大输出小于等于n的素数对,以及对数。

1066. 素数对

题目描述

两个相差为2的素数称为素数对，如5和7，17和19等，本题目要求找出所有两个数均不大于n的素数对。

输入

一个正整数n。1<=n<=10000。

输出

按照从小到大的顺序输出所有小于等于n的素数对。每对素数对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出empty。

样例输入

100

样例输出

3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73

数据范围限制

1<=n<=10000。

C++代码

#include <iostream>
#include <cassert>
#include <cmath>

using namespace std;

bool checkPrime(int n)
{
    if (n <= 1 || n!=2 && n%2==0)
    {
        return false;
    }
    
    for(int i=3; i<=(int)sqrt(double(n)); i++)
    {
        if (n%i == 0)
        {
            return false;
        }
    }

    return true;
}


int main()
{
    const int max_n = 10000;
    int primeList[max_n];
    int n;

    cin >> n;

    assert(n>=1 && n<=max_n);

    for(int i=2; i<=n; i++)
    {
        if (true == checkPrime(i))
        {
            primeList[i] = 1;
        }
        else
        {
            primeList[i] = 0;
        }
    }

    bool primes_pair_found = false;

    for(int i=2; i<=n-2; i++)
    {
        if (primeList[i] == 1 && primeList[i+2] == 1)
        {
            cout << i << " " << i+2 << endl;
            primes_pair_found = true;
        }
    }

    if (false == primes_pair_found)
    {
        cout << "empty" << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65