Sum of numbers in a range [ L , R ] whose count of divisors is prime | Python3 implementation of the approach ; divi [ i ] stores the count of divisors of i ; sum [ i ] will store the sum of all the integers from 0 to i whose count of divisors is prime ; Function for Sieve of Eratosthenes ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be 0 if i is Not a prime , else true . prime [ i ] stores 1 if i is prime ; 0 and 1 is not prime ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiple of p and are less than p ^ 2 are already been marked . ; Function to count the divisors ; For each number i we will go to each of the multiple of i and update the count of divisor of its multiple j as i is one of the factor of j ; Function for pre - computation ; If count of divisors of i is prime ; taking prefix sum ; Driver code ; Find all the prime numbers till N ; Update the count of divisors of all the numbers till N ; Precomputation for the prefix sum array ; Perform query
from math import sqrt NEW_LINE N = 100000 ; NEW_LINE divi = [ 0 ] * N ; NEW_LINE sum = [ 0 ] * N ; NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT prime [ i ] = 1 ; NEW_LINE DEDENT DEDENT prime = [ 1 ] * N ; NEW_LINE INDENT prime [ 0 ] = prime [ 1 ] = 0 ; NEW_LINE for p in range ( 2 , int ( sqrt ( N ) ) + 1 ) : NEW_LINE INDENT if ( prime [ p ] == 1 ) : NEW_LINE INDENT for i in range ( p * p , N , p ) : NEW_LINE INDENT prime [ i ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def DivisorCount ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( i , N , i ) : NEW_LINE INDENT divi [ j ] += 1 ; NEW_LINE DEDENT DEDENT DEDENT def pre ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT if ( prime [ divi [ i ] ] == 1 ) : NEW_LINE INDENT sum [ i ] = i ; NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT sum [ i ] += sum [ i - 1 ] ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT l = 5 ; r = 8 ; NEW_LINE SieveOfEratosthenes ( ) ; NEW_LINE DivisorCount ( ) ; NEW_LINE pre ( ) ; NEW_LINE print ( sum [ r ] - sum [ l - 1 ] ) ; NEW_LINE DEDENT