Что спрашивают
Найдите все простые числа на включённом отрезке [A; B], где B не больше 10^9, а ширина не больше 10 000. Для каждого выведите порядковый номер с единицы и само число.
Простое число имеет ровно два натуральных делителя. Единица простым числом не является. По условию хотя бы одно простое на отрезке существует.
Приём решения
Решето до самого B потребовало бы слишком много памяти. Но любое составное число не больше B имеет простой делитель не больше √B. Сначала найдём только эти малые простые, а затем вычеркнем их кратные в нужном коротком отрезке.
- Постройте обычное решето до isqrt(B).
- Создайте массив длины
B - A + 1; индекс i соответствует числуA + i. - Для каждого малого простого p найдите первое его кратное на отрезке через
((A + p - 1) // p) * p. - Начинайте вычёркивание не раньше p², чтобы не удалить само простое p.
- Отдельно исключите единицу, если она попала в отрезок. Оставшиеся числа перечислите с номера один.
После вычёркивания каждого составного найдётся хотя бы один малый простой делитель, который его отметил. Простое же нельзя удалить как чужое кратное, а собственное 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, старт с 4 | 4, 6, 8, 10, 12, 14, 16 | Само 2 |
| p = 3, старт с 9 | 9, 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)
<algorithm>
<cmath>
<iostream>
<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 занимает последний элемент массива и должно проверяться.
- Нумеровать найденные числа с нуля
Первый столбец ответа начинается с единицы, независимо от положения числа во входном отрезке.