Sum of all Primes in a given range using Sieve of Eratosthenes | CPP program to find sum of primes in range L to R ; prefix [ i ] is going to store sum of primes till i ( including i ) . ; Function to build the prefix sum array ; Create a boolean array " prime [ 0 . . n ] " . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Build prefix array ; Function to return sum of prime in range ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10000 ; int prefix [ MAX + 1 ] ; void buildPrefix ( ) { bool prime [ MAX + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * 2 ; i <= MAX ; i += p ) prime [ i ] = false ; } } prefix [ 0 ] = prefix [ 1 ] = 0 ; for ( int p = 2 ; p <= MAX ; p ++ ) { prefix [ p ] = prefix [ p - 1 ] ; if ( prime [ p ] ) prefix [ p ] += p ; } } int sumPrimeRange ( int L , int R ) { buildPrefix ( ) ; return prefix [ R ] - prefix [ L - 1 ] ; } int main ( ) { int L = 10 , R = 20 ; cout << sumPrimeRange ( L , R ) << endl ; return 0 ; }