Sum of all the prime numbers in a given range | Java Program to compute sum of prime number 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 arr ; 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
public class GFG { static int N = 1000 ; static long dp [ ] = new long [ N + 1 ] ; static void sieve ( ) { int arr [ ] = new int [ N + 1 ] ; arr [ 0 ] = 1 ; arr [ 1 ] = 1 ; for ( int i = 2 ; i <= Math . sqrt ( N ) ; i ++ ) if ( arr [ i ] == 0 ) for ( int j = i * i ; j <= N ; j += i ) arr [ j ] = 1 ; long runningPrimeSum = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( arr [ i ] == 0 ) runningPrimeSum += i ; dp [ i ] = runningPrimeSum ; } } public static void main ( String [ ] args ) { int l = 4 , r = 13 ; sieve ( ) ; System . out . println ( dp [ r ] - dp [ l - 1 ] ) ; } }