Подсчитать все простые числа, которые можно составить из цифр данного числа

Для заданной строки S , состоящей из N цифр, задача состоит в том, чтобы найти количество различных простых чисел, которые можно составить из цифр строки S.

Примеры:

Input: S = “123”
Output: 5
Explanation:
The prime numbers that can be formed from the digits of the string S is 2, 3, 13, 23, and 31. Hence, the total count is 5.

Input: S = “1”
Output: 0

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

• Инициализируйте HashSet H для хранения уникальных возможных строк простых чисел.
• Определите функцию проверки (строковый номер) , чтобы проверить, является ли число простым или нет, и выполните следующие шаги:
  • Если длина строки number[] равна 0 , верните false .
  • Используйте функцию обрезки чтобы обрезать номер.
  • Инициализируйте длинную переменную num и сохраните в ней проанализированное число с помощью функции parseLong.
  • Если num равно 1, вернуть false .
  • Если num%2 равно 0 , а num не равно 2 , верните false .
  • Если num%3 равно 0 , а num не равно 3 , верните false .
  • Переберите диапазон [6, число ^1/2 ], используя переменную i , и выполните следующие шаги:
    • Если одно из значений num%(i-1) или num%(i+1) равно 0 , верните false .
  • В конце верните true .
• Определите функцию DFS(int arr[], string ans) для поиска всех возможных простых чисел и выполните следующие шаги:
  • Вызовите функцию check(ans) и , если функция возвращает true , добавьте эту строку в HashSet H .
  • Переберите диапазон [0, 10], используя переменную i , и выполните следующие шаги:
    • Если arr[i] равно 0, то продолжаем итерацию.
    • Добавьте значение i к строковому ответу и уменьшите значение arr[i] на 1 .
    • Вызовите функцию DFS(arr, ans), чтобы найти другие возможные ответы с возвратом.
    • Удалите значение i из строкового ответа и добавьте значение arr[i] на 1 .
• Инициализируйте массив count[] размером 10 , чтобы сохранить частоту каждого числа в строке S .
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Добавьте частоту на 1 к массиву count[] символа в i ^-м индексе в строке S .
• Вызовите функцию DFS(count, "") , чтобы найти все возможные простые числа.
• После выполнения вышеуказанных шагов выведите размер HashSet H в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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