数学的对数知识

c++内部函数
log2(x)：表示对x取以2为底的对数值
log10(x)：表示对x取以10为底的对数值
cout << log10(1e6); 
log(x)：表示对x取以e为底的对数值，其中e为2.71828...欧拉常数或者自然常数
cout << log(1e6);

素数的个数定理：

1到x中约等于 x/ln(x)个素数

调和级数

1+1/2+1/3+1/4 + ... + 1/x = ln(x)

朴素筛法

核心：把所有数的倍数都筛掉，这个筛法的重要核心！！！ 复杂度

$O(nlog(n))$

bool vis[N + 1];
vector<int> p;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) p.push_back(i);
        for (int j = i * 2; j <= N; j += i) 
            vis[j] = 1;
    }
}

埃氏筛法

核心：每个合数只能由质因子来筛

复杂度

$O(nloglog(n))$

bool vis[N + 1];
vector<int> p;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            p.push_back(i);
            for (int j = i * 2; j <= N; j += i) 
                vis[j] = 1;
        }
    }
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com