思路与算法

用埃氏筛得到不超过n的素数标记。枚举较小数a=2至n-2，若a与a+2都为素数，输出一对。若全程没有输出任何数对，则输出empty。

正确性说明

埃氏筛排除0和1后准确识别全部素数，因为合数都有不超过平方根的素因子且标记不会删掉素数。输出的每对均是两个不超过n且相差2的素数。任一合法数对的较小数均在枚举范围中，必通过条件并恰好输出一次，所以无遗漏或重复。全程没有数对时empty正确。

复杂度

初始化O(n)，筛表O(n log log n)，枚举O(n)，总时间O(n log log n)，额外空间O(n)。n允许1，此时循环为空且标记下标仍合法。

易错点

两个数均需不超过n；第一对是3和5。5可能出现在两对中，不做跨行去重。n小于5输出小写empty；一对内部空格，各对换行。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<bool> prime(n + 1, true);
    prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; ++i)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
    bool found = false;
    for (int i = 2; i + 2 <= n; ++i)
        if (prime[i] && prime[i + 2]) {
            cout << i << ' ' << i + 2 << '\n';
            found = true;
        }
    if (!found)
        cout << "empty\n";
}