Sum of product of proper divisors of all Numbers lying in range [ L , R ] | Python3 implementation to find the sum of the product of proper divisors of all the numbers lying in the range [ L , R ] ; Vector to store the product of the proper divisors of a number ; Variable to store the prefix sum of the product array ; Function to precompute the product of proper divisors of a number at it 's corresponding index ; Modificatino of sieve to store the product of the proper divisors ; Multiplying the existing value with i because i is the proper divisor of ans [ j ] ; Loop to store the prefix sum of the previously computed product array ; Computing the prefix sum ; Function to prthe sum for each query ; Function to prte sum of product of proper divisors of a number in [ L , R ] ; Calling the function that pre computes the sum of product of proper divisors ; Iterate over all Queries to prthe sum ; Driver code
mod = 1000000007 NEW_LINE ans = [ 1 ] * ( 100002 ) NEW_LINE pref = [ 0 ] * 100002 NEW_LINE def preCompute ( ) : NEW_LINE INDENT for i in range ( 2 , 100000 // 2 + 1 ) : NEW_LINE INDENT for j in range ( 2 * i , 100000 + 1 , i ) : NEW_LINE INDENT ans [ j ] = ( ans [ j ] * i ) % mod NEW_LINE DEDENT DEDENT for i in range ( 1 , 100002 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + ans [ i ] NEW_LINE pref [ i ] %= mod NEW_LINE DEDENT DEDENT def printSum ( L , R ) : NEW_LINE INDENT print ( pref [ R ] - pref [ L - 1 ] , end = " ▁ " ) NEW_LINE DEDENT def printSumProper ( arr , Q ) : NEW_LINE INDENT preCompute ( ) NEW_LINE for i in range ( Q ) : NEW_LINE INDENT printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT Q = 2 NEW_LINE arr = [ [ 10 , 20 ] , [ 12 , 16 ] ] NEW_LINE printSumProper ( arr , Q ) NEW_LINE DEDENT