#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 边界处理:n小于3时不可能有素数对(最小素数对是3和5,n至少为5才有)
    if (n < 5) {
        cout << "empty" << endl;
        return 0;
    }

    // 埃氏筛法生成素数标记数组:is_prime[i]为true表示i是素数
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0和1不是素数
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) { // 若i是素数,标记其所有倍数为非素数
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 收集所有素数到列表中
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }

    // 查找素数对并输出,同时标记是否找到
    bool found = false;
    for (int i = 0; i < primes.size() - 1; ++i) {
        if (primes[i + 1] - primes[i] == 2) {
            cout << primes[i] << " " << primes[i + 1] << endl;
            found = true;
        }
    }

    // 未找到素数对则输出empty
    if (!found) {
        cout << "empty" << endl;
    }

    return 0;
}

0 comments

No comments so far...

Information

ID
674
Time
1000ms
Memory
256MiB
Difficulty
2
Tags
(None)
# Submissions
112
Accepted
66
Uploaded By