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

Найдите количество таких перестановок первых N натуральных чисел, что сумма любых двух последовательных чисел является простой, при этом все циклические перестановки считаются одинаковыми.

Примечание . Сумма первого и последнего элементов также должна быть простой.

Пример :

Input: N = 6
Output: 2
Explanation: The two valid permutations are {1, 4, 3, 2, 5, 6} and {1, 6, 5, 2, 3, 4}. The permutation like {3, 2, 5, 6, 1, 4} is considered a cyclic permutation of the 1st one and hence not included.

Input: N = 3
Output: 0
Explanation: No valid permutations exist.

Подход : данная проблема может быть решена с помощью рекурсии и поиска с возвратом. Можно заметить, что для нахождения различного количества циклов без ограничения общности цикл должен начинаться с 1 . Массив isPrime[] можно создать с помощью решета Эратосфена, в котором хранится, является ли число простым или нет. Поэтому создайте рекурсивную функцию и добавьте элементы в перестановку так, чтобы ее сумма с последним элементом была простой. Увеличьте счетчик перестановок, если сумма первого и последнего элементов также является простой.

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

Временная сложность: O(N!)
Вспомогательное пространство: O(1)