Count of numbers in range [ L , R ] which can be represented as sum of two perfect powers | Function to find the number of numbers that can be expressed in the form of the sum of two perfect powers ; Stores all possible powers ; Push 1 and 0 in it ; Iterate over all the exponents ; Iterate over all possible numbers ; This loop will run for a maximum of sqrt ( R ) times ; Push this power in the array pows [ ] ; Increase the number ; Stores if i can be expressed as the sum of perfect power or not ; int ok [ R + 1 ] ; memset ( ok , 0 , sizeof ( ok ) ) ; Iterate over all possible pairs of the array pows [ ] ; The number is valid ; Find the prefix sum of the array ok [ ] ; Return the count of required number ; Driver Code
def TotalPerfectPowerSum ( L , R ) : NEW_LINE INDENT pows = [ ] NEW_LINE pows . append ( 0 ) NEW_LINE pows . append ( 1 ) NEW_LINE for p in range ( 2 , 25 ) : NEW_LINE INDENT num = 2 NEW_LINE while ( ( int ) ( pow ( num , p ) + 0.5 ) <= R ) : NEW_LINE INDENT pows . append ( ( int ) ( pow ( num , p ) + 0.5 ) ) NEW_LINE num = num + 1 NEW_LINE DEDENT DEDENT ok = [ 0 for _ in range ( R + 1 ) ] NEW_LINE for i in range ( 0 , int ( len ( pows ) ) ) : NEW_LINE INDENT for j in range ( 0 , len ( pows ) ) : NEW_LINE INDENT if ( pows [ i ] + pows [ j ] <= R and pows [ i ] + pows [ j ] >= L ) : NEW_LINE INDENT ok [ pows [ i ] + pows [ j ] ] = 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 0 , R + 1 ) : NEW_LINE INDENT ok [ i ] += ok [ i - 1 ] NEW_LINE DEDENT return ok [ R ] - ok [ L - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L = 5 NEW_LINE R = 8 NEW_LINE print ( TotalPerfectPowerSum ( L , R ) ) NEW_LINE DEDENT