Подсчитайте простые числа в диапазоне [L, R], сумма однозначных чисел которых также является простой

Даны два целых числа L и R . Задача состоит в том, чтобы посчитать простые числа в диапазоне [L, R] , единственная сумма которых также является простым числом.
Единая сумма получается путем сложения цифр числа до тех пор, пока не останется одна цифра.

Примеры

Input: L = 5, R = 20 
Output: 3
Explanation: Prime numbers in the range L = 5 to R = 20 are {5, 7, 11, 13, 17, 19}
Their “single sum” of digits is {5, 7, 2, 4, 8, 1}.  
Only {5, 7, 2} are prime. Hence the answer is 3.

Input: L = 1, R = 10  
Output: 4
Explanation: Prime numbers in the range L = 1 to R = 10 are {2, 3, 5, 7}.  
Their “single sum” of digits is {2, 3, 5, 7}.  
Since all the numbers are prime, hence the answer is 4.

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

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

Временная сложность: O((R – L)*N^(1/2)), где N — простое число в диапазоне [L, R].
Вспомогательное пространство: O(1)