Numbers with sum of digits equal to the sum of digits of its all prime factor | maximum size of number ; array to store smallest prime factor of number ; array to store sum of digits of a number ; boolean array to check given number is countable for required answer or not . ; prefix array to store answer ; Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . ; marking smallest prime factor for every number to be itself . ; separately marking spf for every even number as 2 ; checking if i is prime ; marking SPF for all numbers divisible by i ; marking spf [ j ] if it is not previously marked ; Function to find sum of digits in a number ; find sum of digits of all numbers up to MAXN ; add sum of digits of least prime factor and n / spf [ n ] ; if it is valid make isValid true ; prefix sum to compute answer ; Driver code ; print answer for required range ; print answer for required range
MAXN = 100005 NEW_LINE spf = [ 0 ] * MAXN NEW_LINE sum_digits = [ 0 ] * MAXN NEW_LINE isValid = [ 0 ] * MAXN NEW_LINE ans = [ 0 ] * MAXN NEW_LINE def Smallest_prime_factor ( ) : NEW_LINE INDENT for i in range ( 1 , MAXN ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAXN , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT i = 3 NEW_LINE while i * i <= MAXN : NEW_LINE INDENT if ( spf [ i ] == i ) : NEW_LINE INDENT for j in range ( i * i , MAXN , i ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT i += 2 NEW_LINE DEDENT DEDENT def Digit_Sum ( copy ) : NEW_LINE INDENT d = 0 NEW_LINE while ( copy ) : NEW_LINE INDENT d += copy % 10 NEW_LINE copy //= 10 NEW_LINE DEDENT return d NEW_LINE DEDENT def Sum_Of_All_Digits ( ) : NEW_LINE INDENT for n in range ( 2 , MAXN ) : NEW_LINE INDENT sum_digits [ n ] = ( sum_digits [ n // spf [ n ] ] + Digit_Sum ( spf [ n ] ) ) NEW_LINE if ( Digit_Sum ( n ) == sum_digits [ n ] ) : NEW_LINE INDENT isValid [ n ] = True NEW_LINE DEDENT DEDENT for n in range ( 2 , MAXN ) : NEW_LINE INDENT if ( isValid [ n ] ) : NEW_LINE INDENT ans [ n ] = 1 NEW_LINE DEDENT ans [ n ] += ans [ n - 1 ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT Smallest_prime_factor ( ) NEW_LINE Sum_Of_All_Digits ( ) NEW_LINE l = 2 NEW_LINE r = 3 NEW_LINE print ( " Valid ▁ numbers ▁ in ▁ the ▁ range " , l , r , " are " , ans [ r ] - ans [ l - 1 ] ) NEW_LINE l = 2 NEW_LINE r = 10 NEW_LINE print ( " Valid ▁ numbers ▁ in ▁ the ▁ range " , l , r , " are " , ans [ r ] - ans [ l - 1 ] ) NEW_LINE DEDENT