Что спрашивают

Найдите все простые числа на включённом отрезке [A; B], где B не больше 10^9, а ширина не больше 10 000. Для каждого выведите порядковый номер с единицы и само число.

Простое число имеет ровно два натуральных делителя. Единица простым числом не является. По условию хотя бы одно простое на отрезке существует.

Приём решения

Решето до самого B потребовало бы слишком много памяти. Но любое составное число не больше B имеет простой делитель не больше √B. Сначала найдём только эти малые простые, а затем вычеркнем их кратные в нужном коротком отрезке.

  1. Постройте обычное решето до isqrt(B).
  2. Создайте массив длины B - A + 1; индекс i соответствует числу A + i.
  3. Для каждого малого простого p найдите первое его кратное на отрезке через ((A + p - 1) // p) * p.
  4. Начинайте вычёркивание не раньше p², чтобы не удалить само простое p.
  5. Отдельно исключите единицу, если она попала в отрезок. Оставшиеся числа перечислите с номера один.

После вычёркивания каждого составного найдётся хотя бы один малый простой делитель, который его отметил. Простое же нельзя удалить как чужое кратное, а собственное p защищено нижней границей p².

Память — O(√B + W), где W — ширина включённого отрезка. Время состоит из построения малого решета и проходов по кратным: для каждого p выполняется порядка W/p + 1 шагов. Верхняя граница велика, но хранится только небольшой начальный список и сам отрезок.

Разбор на примере

Ввод

2 17

Вывод

1 2
2 3
3 5
4 7
5 11
6 13
7 17
Разбор примера по шагам
ДействиеВычёркиваемСохраняем
p = 2, старт с 44, 6, 8, 10, 12, 14, 16Само 2
p = 3, старт с 99, 12, 15Само 3
После всех проходовСоставные отмечены2, 3, 5, 7, 11, 13, 17

До корня 17 нужны только малые простые 2 и 3. Их собственные значения остаются в массиве, потому что вычёркивание начинается с квадратов. Правая граница 17 тоже включена. Для семи оставшихся простых выводятся номера 1–7.

Код на Python и C++

В массивах хранятся байтовые флаги. Индекс смещён на A, поэтому большое значение границы не означает большой массив.

В C++ флаги отрезка хранятся в vector<bool> длины B - A + 1, первое кратное — (a + p - 1) / p * p. Целый корень считает функция isqrt с поправкой после sqrtl.

import sys
from math import isqrt


def primes_to(limit):
    if limit < 2:
        return []
    flags = bytearray(b'\x01') * (limit + 1)
    flags[0:2] = b'\x00\x00'
    for p in range(2, isqrt(limit) + 1):
        if flags[p]:
            flags[p * p:limit + 1:p] = b'\x00' * ((limit - p * p) // p + 1)
    return [p for p in range(2, limit + 1) if flags[p]]


def solve(a, b):
    flags = bytearray(b'\x01') * (b - a + 1)
    for p in primes_to(isqrt(b)):
        first = max(p * p, (a + p - 1) // p * p)
        if first <= b:
            flags[first - a:b - a + 1:p] = b'\x00' * ((b - first) // p + 1)
    if a == 1:
        flags[0] = 0
    values = [a + i for i, flag in enumerate(flags) if flag]
    return list(enumerate(values, start=1))

if __name__ == '__main__':
    a, b = map(int, sys.stdin.read().split())
    rows = solve(a, b)
    for row in rows:
        print(*row)
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

long long isqrt(long long n) {
    long long r = sqrtl(n);
    while (r * r > n)
        r -= 1;
    while ((r + 1) * (r + 1) <= n)
        r += 1;
    return r;
}

vector<long long> primes_to(long long limit) {
    vector<long long> primes;
    if (limit < 2)
        return primes;
    vector<bool> flags(limit + 1, true);
    for (long long p = 2; p <= limit; p++) {
        if (!flags[p])
            continue;
        primes.push_back(p);
        for (long long k = p * p; k <= limit; k += p)
            flags[k] = false;
    }
    return primes;
}

int main() {
    long long a, b;
    cin >> a >> b;
    vector<bool> flags(b - a + 1, true);
    for (long long p : primes_to(isqrt(b))) {
        long long first = max(p * p, (a + p - 1) / p * p);
        for (long long n = first; n <= b; n += p)
            flags[n - a] = false;
    }
    if (a == 1)
        flags[0] = false;
    int number = 0;
    for (long long i = 0; i <= b - a; i++) {
        if (flags[i]) {
            number += 1;
            cout << number << ' ' << a + i << '\n';
        }
    }
}

Типичные ошибки

  • Считать единицу простой

    У неё только один натуральный делитель. Если A = 1, первый флаг нужно убрать отдельно.

  • Вычеркнуть само малое простое

    Начало с первого кратного без ограничения p² удалит p при попадании его в отрезок.

  • Не включить B

    Отрезок замкнутый: число B занимает последний элемент массива и должно проверяться.

  • Нумеровать найденные числа с нуля

    Первый столбец ответа начинается с единицы, независимо от положения числа во входном отрезке.