Найти простое число чуть меньше и чуть больше каждого элемента данного массива

Для заданного массива целых чисел A[] размера N задача состоит в том, чтобы найти простые числа чуть меньше и чуть больше A[i] (для всех 0<=i<N ).

Примеры:

Input: A={17, 28}, N=2
Output:
13 19
23 29
Explanation:
13 is the prime number just less than 17.
19 is the prime number just greater than 17.
23 is the prime number just less than 28.
29 is the prime number just greater than 28.

Input: A={126, 64, 2896, 156}, N=4
Output:
113 127 
61 67 
2887 2897 
151 157
 

Наивный подход:
Наблюдение: Максимальный изначальный разрыв для чисел меньше 10 ⁹ равен 292.

Наивный подход состоял бы в том, чтобы проверить простоту, проверяя, имеет ли число какой-либо фактор, кроме 1 и самого себя. Выполните следующие шаги, чтобы решить проблему:

Пройдите массив A и для каждого текущего индекса i сделайте следующее:

1. Выполните итерацию от A[i]-1 в порядке убывания и для каждого текущего индекса j сделайте следующее:
   1. Проверьте, является ли j простым или нет, проверив, имеет ли он какой-либо фактор, кроме 1 и самого себя.
   2. Если j простое число, выведите j и завершите внутренний цикл. Это дает простое число чуть меньше, чем A[i] .
2. Выполните итерацию от A[i]+1 в порядке возрастания и для каждого текущего индекса j сделайте следующее:
   1. Проверьте, является ли j простым или нет, проверив, имеет ли он какой-либо фактор, кроме 1 и самого себя.
   2. Если j простое число, выведите j и завершите внутренний цикл. Это дает простое число чуть меньше A[i],

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*G*√M), где G — максимальный простой разрыв, а M — самый большой элемент в A.
Вспомогательное пространство: O(1)

Эффективный подход 1: вместо проверки отдельных чисел все простые числа можно пересчитать с помощью решета Эратосфена.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*G+MLog(Log(M))), где G — максимальный простой разрыв, а M — самый большой элемент в A.
Вспомогательное пространство: O(M)

Эффективный подход 2: можно использовать критерий простоты Миллара-Рабина.

Временная сложность: O(N*G*KLog ³ M), где G – максимальный основной разрыв, а M – самый большой элемент в A. Здесь K=4 .
Вспомогательное пространство: O(1)