跳转至

欧拉筛质数

868.筛质数

给点一个正整数 \(n\)，请你求出 \(1 \sim n\) 中的质数个数。

欧拉筛法：

  • 给点一个正整数 \(n\)；
  • 先创建两个数组：\(pm[N]\)、\(dt[N]\)，分别代表质数数组，和用于筛数的数组；
  • 用指针 \(i\) 从 2 开始向右遍历；
  • 如果 \(dt[i] == 0\) 就代表 \(i\) 是质数
    • 先将 \(i\) 装进 \(pm[N]\) 的尾部；
  • 不管 \(i\) 是不是质数，都要用 \(j\) 从 \(pm[N]\) 的头部开始向右遍历，不断的筛去 \(dt[pm[j] * i] = 1\)
    • 当然若 \(pm[j] * i > n\) 就没有筛的必要了，直接退出循环。
    • 筛去 \(dt[pm[j] * i] = 1\) 了之后，如果 \(i \bmod pm[j] == 0\) 也要退出循环。

由于每个数只被筛一次，所以「时间复杂度」是：\(O(n)\)。

代码参考：

const int N = int (1e7 + 10);
int pm[N], dt[N], cnt;

void get_p(int n)
{
    if (n <= 1) return;
    for (int i = 2; i <= n; i ++)
    {
        if (!dt[i]) pm[cnt ++] = i;
        for (int j = 0; pm[j] <= n / i; j ++)
        {
            dt[pm[j] * i] = 1; 
            if (!(i % pm[j])) break;
        }
    }
}
868.筛质数

给点一个正整数 \(n\)，请你求出 \(1 \sim n\) 中的质数个数。

#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

const int N = int (1e7 + 10);
int pm[N], dt[N], cnt;

void get_p(int n)
{
    if (n <= 1) return;
    for (int i = 2; i <= n; i ++)
    {
        if (!dt[i]) pm[cnt ++] = i;
        for (int j = 0; pm[j] <= n / i; j ++)
        {
            dt[pm[j] * i] = 1; 
            if (!(i % pm[j])) break;
        }
    }
}

void solve(void)
{
    int n; scanf ("%d", &n);
    get_p(n); printf ("%d\n", cnt);
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}