Count of Perfect Numbers in given range for Q queries | python 3 program for the above approach ; Function to check whether a number is perfect Number ; Stores sum of divisors ; Itearate over the range [ 2 , sqrt ( N ) ] ; If sum of divisors is equal to N , then N is a perfect number ; Function to find count of perfect numbers in a given range ; Stores the count of perfect Numbers upto a every number less than MAX ; Iterate over the range [ 1 , MAX ] ; Traverse the array arr [ ] ; Print the count of perfect numbers in the range [ arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ] ; Driver Code
MAX = 100005 NEW_LINE from math import sqrt NEW_LINE def isPerfect ( N ) : NEW_LINE INDENT sum = 1 NEW_LINE for i in range ( 2 , int ( sqrt ( N ) ) + 1 , 1 ) : NEW_LINE INDENT if ( N % i == 0 ) : NEW_LINE INDENT if ( i * i != N ) : NEW_LINE INDENT sum = sum + i + N // i NEW_LINE DEDENT else : NEW_LINE INDENT sum = sum + i NEW_LINE DEDENT DEDENT DEDENT if ( sum == N and N != 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def Query ( arr , N ) : NEW_LINE INDENT prefix = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE for i in range ( 2 , MAX + 1 , 1 ) : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] + isPerfect ( i ) NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT print ( prefix [ arr [ i ] [ 1 ] ] - prefix [ arr [ i ] [ 0 ] - 1 ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 1 , 1000 ] , [ 1000 , 2000 ] , [ 2000 , 3000 ] ] NEW_LINE N = len ( arr ) NEW_LINE Query ( arr , N ) NEW_LINE DEDENT