Sum of all the prime numbers in a given range | Suppose the constraint is N <= 1000 ; Declare an array for dynamic approach ; Method to compute the array ; Declare an extra array as array ; Iterate the loop till sqrt ( N ) Time Complexity is O ( log ( n ) X sqrt ( N ) ) ; if ith element of arr is 0 i . e . marked as prime ; mark all of it 's multiples till N as  non-prime by setting the locations to 1 ; Update the array ' dp ' with the running sum of prime numbers within the range [ 1 , N ] Time Complexity is O ( n ) ; Here , dp [ i ] is the sum of all the prime numbers within the range [ 1 , i ] ; Driver Code ; Compute dp
N = 1000 NEW_LINE dp = [ 0 ] * ( N + 1 ) NEW_LINE def sieve ( ) : NEW_LINE INDENT array = [ 0 ] * ( N + 1 ) NEW_LINE array [ 0 ] = 1 NEW_LINE array [ 1 ] = 1 NEW_LINE for i in range ( 2 , math . ceil ( math . sqrt ( N ) + 1 ) ) : NEW_LINE INDENT if array [ i ] == 0 : NEW_LINE INDENT for j in range ( i * i , N + 1 , i ) : NEW_LINE INDENT array [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT runningPrimeSum = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if array [ i ] == 0 : NEW_LINE INDENT runningPrimeSum += i NEW_LINE DEDENT dp [ i ] = runningPrimeSum NEW_LINE DEDENT DEDENT l = 4 NEW_LINE r = 13 NEW_LINE sieve ( ) NEW_LINE print ( dp [ r ] - dp [ l - 1 ] ) NEW_LINE