时间戳

首页 > 解决方案 > 素数生成器不适用于小数

c++ - 素数生成器不适用于小数

问题描述

两天以来，我一直在努力解决 SPOJ 的 PRIME1 问题。我设法编写了一个适用于大数字的程序，但我无法弄清楚为什么它会在开始范围（通常是 1-11）中显示如此混乱的数字。我正在使用 Eratosthenes 的分段筛。 SPOJ 链接

这是问题所在：

输入

输入以单行中的测试用例数量 t (t<=10) 开始。在接下来的 t 行中的每一行中，都有两个数字 m 和 n (1 <= m <= n <= 1000000000, nm<=100000)，由空格分隔。

输出

对于每个测试用例，打印所有质数 p，使得 m <= p <= n，每行一个数字，测试用例用空行分隔。

我的代码：

#include <bits/stdc++.h>
using namespace std;

#define MAX         1000000000
#define MAX_SQRT    sqrt(MAX)

vector<bool> is_prime(MAX_SQRT, true);

void simpleSieve(int limit, vector<int>& primes)
{
    for(int p=2; p*p<=limit; p++) {
        if(is_prime[p] == true) {
            for(int i=p*p; i<=limit; i+=p)
                is_prime[i] = false;
        }
    }
    for(int i=2; i<=limit; i++) {
        if(is_prime[i]) primes.push_back(i);
    }
}

void segmentedSieve(int left, int right)
{
    int range = floor(sqrt(right)) + 1;
    vector<int> primes;
    simpleSieve(range, primes);

    int n = right - left + 1;

    bool sieve[n];
    memset(sieve, true, sizeof(sieve));

    for (int i = 0; i<primes.size(); i++) {

        int low = floor(left/primes[i]) * primes[i];
        if(low < left)
            low += primes[i];

        for(int a=low; a<=right; a+=primes[i]) {
            sieve[a - left] = false;
        }
    }
    for(int i=left; i<=right; i++)
        if(sieve[i - left])   cout << i << "\n";
}

int main()
{
    int t;
    cin >> t;
    while(t--) {
        int left, right;
        cin >> left >> right;
        segmentedSieve(left, right);
    }
    return 0;
}

我已经尝试硬编码开始部分，但它会有所不同，具体取决于输入。

标签： c++c++11primessieve-of-eratosthenes

解决方案

首先打印使用 simpleSieve 生成​​的大于左的素数。
此外，1 不是素数，因此我们将在打印其他素数时跳过它：

for (int i = 0; i<primes.size(); i++) {
    if (primes[i] >= left)
        cout << primes[i] << "\n";
}

for(int i=left; i<=right; i++){
    if (i == 1){
        continue;
    }
    if(sieve[i - left])   cout << i << "\n";
}
cout << "\n";  //empty line before next testcase starts

推荐阅读