线性筛

线性筛是一种用于求解质数的算法，它的时间复杂度为O(n)。其基本思想是从小到大枚举每个数，如果这个数是质数，就将其加入到质数序列中，并将其倍数标记为合数。这样，每个合数都只会被其最小质因子筛掉，而没有被重复筛掉。最终筛完后，留下的就是所有的质数。

具体的实现方法是，使用一个布尔数组标记每个数是否为质数，初始化时全部设为true。从2开始枚举每个数，如果它是质数，则将其加入质数序列中，并将其倍数全部标记为合数。最终所有没有被标记为合数的数都是质数。

以下是C++实现代码：

const int MAXN = 1e6 + 5;
bool is_prime[MAXN];
vector<int> primes;

void linear_sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

相关问题

python 线性筛

Python线性筛法是一种用于找出一定范围内所有质数的算法。它的基本思想是通过筛除合数的方式来找出质数。具体步骤如下：

1. 首先，我们定义一个长度为N的布尔数组st，用来标记每个数是否为质数。
2. 初始化一个长度为N的空数组primes，用来存储找到的质数。
3. 从2开始遍历到N-1，如果当前数i不是合数（即st[i]为False），则将其加入primes数组，并将质数计数器cnt加1。
4. 对于每个质数primes[j]，遍历范围为j从0到cnt-1，如果primes[j]乘以i超过了N，则跳出循环。
5. 在内层循环中，将合数primes[j]*i标记为True，同时判断i是否能整除primes[j]，如果是则跳出内层循环。
6. 最后，输出质数的个数cnt。

以上就是Python线性筛法的基本原理和步骤。通过这种方法，我们可以高效地找出一定范围内的所有质数。

dev c++线性筛

线性筛是一种用于求解素数的算法，它可以在O(n)的时间复杂度内求出n以内的所有素数。Dev C++是一个集成开发环境，可以用来编写和调试C++程序。因此，我们可以使用Dev C++来实现线性筛算法。
在Dev C++中实现线性筛算法的步骤如下：
1. 创建一个新的C++项目。
2. 在项目中创建一个新的源文件。
3. 在源文件中编写线性筛算法的代码。
4. 编译并运行程序。
具体的代码实现可以参考以下步骤：
1. 首先，我们需要定义一个数组来存储素数。由于线性筛算法是从小到大依次筛选素数，因此我们可以使用一个布尔类型的数组来表示每个数是否为素数。
2. 然后，我们需要使用一个循环来遍历2到n之间的所有数，将所有素数的倍数标记为非素数。
3. 最后，我们可以使用一个循环来输出所有素数。
下面是一个简单的Dev C++线性筛实现的代码示例：

#include <iostream>
using namespace std;

const int MAXN = 1000000;
bool isPrime[MAXN + 1];
int prime[MAXN + 1], cnt = 0;

void linearSieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    linearSieve(n);
    for (int i = 1; i <= cnt; i++) {
        cout << prime[i] << " ";
    }
    return 0;
}