Найти все простые числа в диапазоне [A; B]

Задача:

Найти все простые числа в диапазоне от А до В (1 <= A <= B <= 10^12 ), при условии, что В - А >= 10 ^ 6. Уже 4 день ломаю над этим голову. Есть решение на С++ с помощью Решета Эратосфена.

Решение:

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

Описание решения:

Находим все простые на отрезке [0; b - a] за О(10^6 log log 10^6), с помощью остатков от деления переносим эти простые на отрезок [a; b].

Проблема:

Решение не работает на каких-то тестах (т.е решение неполное). Тесты, к сожалению, неизвестны.