- 素数对
ok
- @ 2026-1-7 19:37:04
#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