洛谷 P1304 哥德巴赫猜想

首先来看题分析这道题要求从4开始验证哥德巴赫猜想主要考察验证素数质数最基本的做法如下#include bits/stdc.h using namespace std; bool isPrime(int n) { // 判断是否为质数 if (n 2) return false; for (int i 2; i sqrt(n); i) { if (n % i 0) return false; } return true; } int main() { int n; cin n; for (int i 4; i N; i 2) // 遍历偶数 for (int j 2; j i/2; j) // 遍历可能的第一个质数 if (isPrime(j) isPrime(i - j)) { cout i j (i - j) endl; break; // 找到第一个最小加数的组合后跳出 } return 0; }但是这样非常地耗时间成本很大所以有多种优化方案减少循环次数只遍历奇数作为第一个质数除了2因为偶数除了2以外不可能是质数预处理素数可避免素数的Prime函数调用过多次即先把所有素数全部列出来函数如下#define N 10005; bool primes[N]; void getprime(int n) { primes[0] primes[1] true; for (int i 2; i * i n; i) { if (primes[i]) continue; for (int j i * i; j n; j i) primes[j] true; } }最终code#include bits/stdc.h using namespace std; #define N 10005; bool primes[N]; void getprime(int n) { primes[0] primes[1] true; for (int i 2; i * i n; i) { if (primes[i]) continue; for (int j i * i; j n; j i) primes[j] true; } } int main() { int n; scanf(%d, n); getprime(n); for (int i 4; i n; i 2) for (int j 1; j n / 2; j ) { if (!primes[j] !primes[i - j]) printf(%d%d%d, i, j, i-j); } return 0; }