primes

Возвращает таблицу с единственным столбцом prime, содержащим простые числа.

• primes() – Возвращает бесконечную таблицу с единственным столбцом prime (UInt64), содержащим простые числа в порядке возрастания, начиная с 2. Используйте LIMIT (и при необходимости OFFSET), чтобы ограничить число строк.

• primes(N) – Возвращает таблицу с единственным столбцом prime (UInt64), содержащим первые N простых чисел, начиная с 2.

• primes(N, M) – Возвращает таблицу с единственным столбцом prime (UInt64), содержащим M простых чисел, начиная с N-го простого числа (индексация с 0).

• primes(N, M, S) – Возвращает таблицу с единственным столбцом prime (UInt64), содержащим M простых чисел, начиная с N-го простого числа (индексация с 0), с шагом S по индексу простого числа. Возвращаемые простые числа соответствуют индексам N, N + S, N + 2S, ..., N + (M - 1)S. S должно быть >= 1.

Это аналогично системной таблице system.primes.

Следующие запросы эквивалентны:

SELECT * FROM primes(10);
SELECT * FROM primes(0, 10);
SELECT * FROM primes() LIMIT 10;
SELECT * FROM system.primes LIMIT 10;
SELECT * FROM system.primes WHERE prime IN (2, 3, 5, 7, 11, 13, 17, 19, 23, 29);

Следующие запросы также эквивалентны:

SELECT * FROM primes(10, 10);
SELECT * FROM primes() LIMIT 10 OFFSET 10;
SELECT * FROM system.primes LIMIT 10 OFFSET 10;

​

Примеры

Первые 10 простых чисел.

SELECT * FROM primes(10);

  ┌─prime─┐
  │     2 │
  │     3 │
  │     5 │
  │     7 │
  │    11 │
  │    13 │
  │    17 │
  │    19 │
  │    23 │
  │    29 │
  └───────┘

Первое простое число больше 1e15.

SELECT prime FROM primes() WHERE prime > 1e15 LIMIT 1;

  ┌────────────prime─┐
  │ 1000000000000037 │ -- 1.00 quadrillion
  └──────────────────┘

Решите ограничение по модулю для простых чисел в очень большом диапазоне: найдите первое простое число p >= 10^15, для которого p по модулю 65537 равно 1.

SELECT prime
FROM primes()
WHERE prime >= 1e15
  AND prime % 65537 = 1
LIMIT 1;

 ┌────────────prime─┐
 │ 1000000001218399 │ -- 1.00 quadrillion
 └──────────────────┘

Первые 7 чисел Мерсенна, являющихся простыми.

SELECT prime
FROM primes()
WHERE bitAnd(prime, prime + 1) = 0
LIMIT 7;

  ┌──prime─┐
  │      3 │
  │      7 │
  │     31 │
  │    127 │
  │   8191 │
  │ 131071 │
  │ 524287 │
  └────────┘

​

Примечания

• Самые быстрые варианты — обычные запросы по диапазону и запросы с точечным фильтром, использующие шаг по умолчанию (1), например primes(N) или primes() LIMIT N. В них используется оптимизированный генератор простых чисел, который позволяет эффективно вычислять очень большие простые числа.
• Для неограниченных источников (primes() / system.primes) простые фильтры по значению, такие как prime BETWEEN ..., prime IN (...) или prime = ..., можно применять прямо в процессе генерации, чтобы сузить диапазоны поиска. Например, следующий запрос выполняется почти мгновенно:

SELECT sum(prime)
FROM primes()
WHERE prime BETWEEN 1e6 AND 1e6 + 100
   OR prime BETWEEN 1e12 AND 1e12 + 100
   OR prime BETWEEN 1e15 AND 1e15 + 100
   OR prime IN (9999999967, 9999999971, 9999999973)
   OR prime = 1000000000000037;

  ┌───────sum(prime)─┐
  │ 2004010006000641 │ -- 2.00 квадриллиона
  └──────────────────┘

1 row in set. Elapsed: 0.090 sec. 

• Эта оптимизация диапазона значений не применяется к ограниченным табличным функциям (primes(N), primes(offset, count[, step])) с WHERE, поскольку эти варианты задают конечную таблицу по индексу простых чисел, и для сохранения семантики фильтр должен вычисляться после генерации этой таблицы.
• Использование ненулевого смещения и/или шага больше 1 (primes(offset, count) / primes(offset, count, step)) может работать медленнее, поскольку внутри может потребоваться сгенерировать и пропустить дополнительные простые числа. Если смещение или шаг вам не нужны, опустите их.