Генератор простых чисел не работает для небольших чисел - PullRequest
Новая
       61

Генератор простых чисел не работает для небольших чисел

0 голосов
/ 10 декабря 2018

Уже 2 дня я борюсь с проблемой PRIME1 от SPOJ.Мне удалось написать программу, которая отлично работает для больших чисел, но я не могу понять, почему она отображает такие запутанные числа в начальном диапазоне (обычно 1-11).Я использую Сегментированное Сито Эратосфена. SPOJ link

Вот проблема:

Вход

Вход начинается с числа t тестовых случаевв одной строке (t <= 10).В каждой из следующих t строк есть два числа m и n (1 <= m <= n <= 1000000000, nm <= 100000), разделенные пробелом. </p>

Выход

Для каждого тестового примера выведите все простые числа p, такие что m <= p <= n, по одному числу в строке, тестовые случаи отделены пустой строкой. </p>

И мой код:

#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;
}

Я пытался жестко запрограммировать начальную часть, но она варьируется в зависимости от ввода.

1 Ответ

0 голосов
/ 10 декабря 2018

Сначала выведите простые числа больше левых, которые были сгенерированы с использованием 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
...