源自项目:2020贵软自无转系面试题参考答案

其中有个面试题,问如何求1~1000以内的素数,由于数据规模小,可以用“土办法”。但如果把1000改为更大的数,就需要用到素数筛了。参考回答如下。后附实现代码。

埃氏筛

可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组,数组的下标对应N以内的数,先把数组初始化为全0,意味着是素数。接下来,从i=2开始遍历这些数,如果它的布尔标记为0,那么就把它的2倍、它的3倍、……一直到N以内最大的它的整数倍为止,将这些数都标记为1,意思是不是素数。如果i已经被标记为1,那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。(0、1除外。)时间复杂度为O(n*log(log(n)))。

(改进版:)

可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组,数组的下标对应N以内的数,先把数组初始化为全0,意味着是素数。接下来,从i=2开始遍历这些数,如果它的布尔标记为0,那么从j=i*i开始,每次j递增i,将j对应的数都标记为1,意思是不是素数,直到j大于N。如果i已经被标记为1,那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。(0、1除外。)时间复杂度为O(n*log(log(n)))。

(大佬们可以继续前进!如果问你不是1000而是300000000呢?)

欧拉筛

可以采用欧拉线性筛的方式。开两个长度为(N+1)的数组,一个为bool型,初始化为0,用于标记是否是素数;另一个int型,名为prime,初始化为全0,用于存储已经找到的素数。从i=2开始,我们用外层循环遍历每一个数,如果i的标记是0,那么把i添加进记录素数的数组中;然后无论i的标记,开启内层循环,令j=0,开始遍历prime中存的每一个素数prime[j],将i*prime[j]都标记为1。一直循环到某次i%prime[j]等于0,终止内层循环,继续外层循环,直至i>N结束外层循环。最后N以内的素数就是保存在prime数组中前面的非零数。

本算法时间复杂度为O(n),因此称为线性筛。其中优化的原理在于每个合数都只被它最小的质因子筛去,减少了不必要的重复。

欧拉筛的关键代码是

if (i % primes[j] == 0) // most important
    break;

它的目的是保证每个合数都只被它最小的质因子筛去。

比如,i=15时,会依次筛掉i*primes[0]=15*2=30,和i*primes[1]=15*3=45。而此时i%primes[1]=15%3=0,因此会break,于是i*primes[2]=15*5=75就不会在i=15时筛掉;75会被它最小的质因子3筛掉,也就是i=25时,被i*primes[1]=25*3=75筛掉。

为什么呢?简单来说,当i%primes[j]=0时,i有质因子primes[j]。接下来是准备用primes[j+1]筛掉i*primes[j+1];而由于i有质因子primes[j]i*primes[j+1]就有质因子primes[j];同时,i*primes[j+1]有质因子primes[j+1],且primes[j]<primes[j+1]。因此如果用primes[j+1]筛掉i*primes[j+1],而不是用primes[j]筛掉i*primes[j+1],就不满足“保证每个合数都只被它最小的质因子筛去”了。因此当i%primes[j]=0时就需要break

以上内容的严谨证明请参阅参考资料。

实现

改进版埃氏筛:

//  Created by Colin on 2020/05/17.
//  Copyright © 2020 Colin. All rights reserved.
//  https://blog.valderfield.com/archives/35/
#include <iostream>
using namespace std;

void E_sieve(const int N, bool* not_prime)
{
    not_prime[0] = not_prime[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!not_prime[i])
        {
            auto j = (long long)i * i;    // j may exceed int !!!
            if (j <= N)
                for (; j <= N; j += i)
                    not_prime[j] = 1;
        }
    }
}

int main()
{
    bool not_prime[1000001] = { 0 };
    int n;
    cin >> n;
    E_sieve(n, not_prime);
    for (int i = 2; i <= n; i++)
    {
        if (!not_prime[i])
            cout << i << ' ';
    }
    cout << endl;
    
    return 0;
}

欧拉筛:

//  Created by Colin on 2020/05/17.
//  Copyright © 2020 Colin. All rights reserved.
//  https://blog.valderfield.com/archives/35/
#include <iostream>
#include <vector>
using namespace std;

void Euler_sieve(const int N, vector<int>& primes)
{
    bool not_prime[1000001] = { 0 };
    not_prime[0] = not_prime[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!not_prime[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= N; j++)
        {
            not_prime[i * primes[j]] = 1;
            if (i % primes[j] == 0) // most important
                break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> primes;
    Euler_sieve(n, primes);
    for (auto x : primes)   // supported by C++11
        cout << x << ' ';
    cout << endl;
    
    return 0;
}

参考资料:

关于求素数的思路(一般筛法到线性筛)

OI Wiki - 筛法(利益无关,友情安利。)

欧拉线性筛法求素数(顺便实现欧拉函数的求值)

埃拉托色尼筛法的复杂度估计与改进 及线性时间筛法简介

Last modification:May 17th, 2020 at 05:23 pm
如果觉得我的文章对你有用,请随意赞赏