Count Primes in Ranges | CPP program to answer queries for count of primes in given range . ; prefix [ i ] is going to store count of primes till i ( including i ) . ; 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 ; Returns count of primes in range from L to R ( both inclusive ) . ; 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 ] ++ ; } } int query ( int L , int R ) { return prefix [ R ] - prefix [ L - 1 ] ; } int main ( ) { buildPrefix ( ) ; int L = 5 , R = 10 ; cout << query ( L , R ) << endl ; L = 1 , R = 10 ; cout << query ( L , R ) << endl ; return 0 ; }