Count all prime numbers in a given range whose sum of digits is also prime | Python3 program for the above approach ; Create an array for storing primes ; Create a prefix array that will contain whether sum is prime or not ; Function to find primes in the range and check whether the sum of digits of a prime number is prime or not ; Initialise Prime array arr [ ] ; Since 0 and 1 are not prime numbers we mark them as '0 ; Using Sieve Of Eratosthenes ; If the number is prime ; Mark all the multiples of i starting from square of i with '0' ie . composite ; '0' represents not prime ; Initialise a sum variable as 0 ; Check if the number is prime ; A temporary variable to store the number ; Loop to calculate the sum of digits ; Check if the sum of prime number is prime ; If prime mark 1 ; If not prime mark 0 ; Computing prefix array ; Function to count the prime numbers in the range [ L , R ] ; Function call to find primes ; Print the result ; Driver Code ; Input range ; Function call
maxN = 1000000 NEW_LINE arr = [ 0 ] * ( 1000001 ) NEW_LINE prefix = [ 0 ] * ( 1000001 ) NEW_LINE def findPrimes ( ) : NEW_LINE INDENT for i in range ( 1 , maxN + 1 ) : NEW_LINE INDENT arr [ i ] = 1 NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT arr [ 0 ] = 0 NEW_LINE arr [ 1 ] = 0 NEW_LINE i = 2 NEW_LINE while i * i <= maxN : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT for j in range ( i * i , maxN , i ) : NEW_LINE INDENT arr [ j ] = 0 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT sum = 0 NEW_LINE prefix [ 0 ] = 0 NEW_LINE for i in range ( 1 , maxN + 1 ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT temp = i NEW_LINE sum = 0 NEW_LINE while ( temp > 0 ) : NEW_LINE INDENT x = temp % 10 NEW_LINE sum += x NEW_LINE temp = temp // 10 NEW_LINE if ( arr [ sum ] == 1 ) : NEW_LINE INDENT prefix [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] = 0 NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( 1 , maxN + 1 ) : NEW_LINE INDENT prefix [ i ] += prefix [ i - 1 ] NEW_LINE DEDENT DEDENT def countNumbersInRange ( l , r ) : NEW_LINE INDENT findPrimes ( ) NEW_LINE result = ( prefix [ r ] - prefix [ l - 1 ] ) NEW_LINE print ( result ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT l = 5 NEW_LINE r = 20 NEW_LINE countNumbersInRange ( l , r ) NEW_LINE DEDENT