数论: 质数筛法

Posted on Edited on In , Word count in article: 287 Reading time ≈ 1 mins.

埃氏筛法

  • 埃氏筛法，全名埃拉托斯特尼筛法 若一个数是素数，那么必然不可能存在有除1和它自身的因子，也就是比它小的数(除了1)都无法整除它 那么，从小到大遍历除1外的正整数，将所有素因子的倍数都标记上，如果遍历到一个数i，它没有被标记，那么它就是素数；初始时，notprime[2]=false(即2是素数)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool notprime[MAXN];
    void getPrime() {
        for (int i = 2; i < MAXN; ++i) {
            if (!notprime[i]) { // 说明它是素数
                for (int j = 2; i * j <= MAXN; ++j) {
                    notprime[i * j] = true;
                }
            }
        }
    }

    可以简单地写出时间表达式：$\begin{align}\left\lfloor\frac{N}{2}\right\rfloor+\left\lfloor\frac{N}{3}\right\rfloor+\left\lfloor\frac{N}{5}\right\rfloor+\cdots+\left\lfloor\frac{N}{p}\right\rfloor\end{align}$，p为小于或等于MAXN的最大质数，证明过程是很难的，只需要知道埃氏筛法的时间复杂度为O(nlog(log(n)))即可 也就是说，在106数量级内，且需要快速判断一个大范围内的素数时，埃氏筛法是有效的

欧拉筛法