AcWing 1292. 哥德巴赫猜想

题目传送门

埃筛时间复杂度

\(O(nlg(n)lg(n))\)

质数个数定理

\(1\sim n\)之间质数的个数是\(\frac{ln(n)}{n}\)

调和级数

\(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=lgn+L\)
上面的式子被称为调和级数,其中\(L\)是一个常数，被称为欧拉常数，是无理数还是有理数还没有被证明出来,大约值是\(0.577\),大概率是一个无理数。

其实也可以记一下：\(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}...+\frac{1}{n}\)(\(n\)是质数)这个计算的时间复杂度为\(loglogn\),这个时间复杂度是很牛\(B\)的，可以视为\(O(1)\)

实现代码

#include 
using namespace std;

//欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int main() {
    get_primes(N - 1); //不能到N，因为数组下标从0开始！要不会越界~

    int n;
    while (scanf("%d", &n), n) { //用逗号比用 && 少一个输入字符~
        for (int i = 1;; i++) {  //不断枚举每个奇数质数,不用上界，因为认为哥德巴赫猜想是正确的，肯定有解
            int a = primes[i];   //放过数字2
            int b = n - a;       //差值
            if (!st[b]) {        //差值也是质数
                printf("%d = %d + %d\n", n, a, b);
                break;
            }
        }
    }

    return 0;
}