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

Учитывая массив arr[] размера N , содержащий только положительные элементы, задача состоит в том, чтобы найти количество простых чисел, меньшее, чем число, сформированное после выполнения следующих операций:

• Добавьте все элементы данного массива, скажем, сумму
• Замените каждую цифру суммы с общим количеством простых чисел, встречающихся между 0 и этой цифрой.

Примеры:

Input: N = 5, arr[] = {7, 12, 9, 27, 1}
Output: 11
Explanation: Sum of all element is 56. 
The prime numbers between [0, 5] and [0, 6] are 3, which are (2, 3, 5). 
So, the new number becomes 33. 
Now the total prime numbers between [0, 33] are11. 
So the final answer will be 11.

Input: N = 4, arr[] = {1, 2, 3, 4}
Output: 0

Алгоритм: Это простая проблема, основанная на реализации. Идея состоит в том, чтобы выполнять операции одну за другой, как уже упоминалось, и, наконец, подсчитывать количество простых чисел.

Выполните шаги, указанные ниже, чтобы решить проблему.

• Найдите общую сумму заданного массива.
• Преобразуйте сумму в строку, скажем, S .
• Переберите строку и замените каждый символ количеством простых чисел от 0 до этого символа.
• Преобразуйте вновь сформированную строку в целое число Y.
• Подсчитайте общее количество простых чисел от 0 до Y и верните его.

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

Сложность времени: НА)
Вспомогательное пространство: О(1)