c++ – Find all primes in the range [A; B]

Question:

Task:

Find all primes in the range A to B ( 1 <= A <= B <= 10 ^ 12 ), provided B – A <= 10 ^ 6 . I've been racking my brains over this for 4 days already. There is a C ++ solution using the Sieve of Eratosthenes .

Solution:

#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;

const ll MAXN = 1e6 + 1;

int main() {
    cin.tie(0); //Ускоряем cin
    cout.tie(0); //Ускоряем cout
    ll a, b;
    cin >> a >> b; //Получаем числа

    bool prime[MAXN], ans[MAXN]; //ans[i] - является ли число a + i простым
    memset(prime, true, MAXN);
    memset(ans, true, MAXN);
    prime[0] = prime[1] = false;

    //Оба вложенных цикла взяты из кода по ссылку (стандартная реализация решета Эратосфена)
    ll n = MAXN - 1;
    for (ll i = 2; i <= n; ++i) {
        if (prime[i]) {
            ll r = a % i;
            r = (i - r) % i; //Что нужно прибавить к а, чтобы получить непростое число

            if (a + r > i && r < MAXN) //Проверяем на выход из массива. Если убрать условие а + r > i, тогда алгоритм отмечает 2, 3, 5 как не простые
                ans[r] = false;

            if (i + r < MAXN && a + r + i > 1ll * i)
                ans[i + r] = false;
            for (ll j = i * i; j <= n; j += i) {
                prime[j] = false;
                if (a <= j && j - a < MAXN) //Если а < 10 ^ 6 (бех этой проверки не работает)
                    ans[j - a] = false;
                if (j + r < MAXN)
                    ans[j + r] = false;
            }
        }
    }
    
    //Выводим результат
    for (ll i = 0; i <= b - a; ++i) {
        if (ans[i] && a + i >= 2)
            cout << a + i << ' ';
    }
}

Solution Description:

Find all primes on the segment [0; b – a] behind O (10 ^ 6 log log 10 ^ 6) , using the remainder of the division, transfer these primes to the segment [a; b].

Problem:

The solution does not work on some tests (i.e. the solution is incomplete ). Unfortunately, the tests are unknown.

Answer:

I began to conduct tests on large numbers and noticed that often 1-2 difficult ones fall. I don't know why, but replacing j = i * i with j = 2 * i fixed everything, and the program did not work for more than 40 ms.

Complete solution code:

#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;

const ll MAXN = 1e6 + 1;
ll max(ll a, ll b) {
    return a > b ? a : b;
}

int main() {
    //cin.tie(0); //Ускоряем cin
    //cout.tie(0); //Ускоряем cout
    ll a, b;
    cin >> a >> b; //Получаем числа

    bool prime[MAXN], ans[MAXN]; //ans[i] - является ли число a + i простым
    memset(prime, true, MAXN);
    memset(ans, true, MAXN);
    prime[0] = prime[1] = false;

    ll mmax = MAXN - 1;
    for (ll i = 2; i <= mmax; ++i) {
        if (prime[i]) {
            ll r = a % i;
            r = (i - r) % i; //Что нужно прибавить к а, чтобы получить непростое число

            if (a + r > i && r < MAXN) //Проверяем на выход из массива. Если убрать условие а + r > i, тогда алгоритм отмечает 2, 3, 5 как не простые
                ans[r] = false;

            if (i + r < MAXN && a + r + i > i)
                ans[i + r] = false;
            for (ll j = 2 * i; j <= mmax; j += i) {
                prime[j] = false;
                if (a <= j && j - a < MAXN) //Если а < 10 ^ 6 (бех этой проверки не работает)
                    ans[j - a] = false;
                if (j + r < MAXN) {
                    ans[j + r] = false;
                }
            }
        }
    }

    //Выводим результат
    for (ll i = 0; i <= b - a; ++i) {
        if (ans[i] && a + i >= 2)
            cout << a + i << ' ';
    }
}
Post Views: 0
Scroll to Top