Count Primes in Ranges | C # 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
using System ; class GFG { static int MAX = 10000 ; static int [ ] prefix = new int [ MAX + 1 ] ; static void buildPrefix ( ) { bool [ ] prime = new bool [ MAX + 1 ] ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == false ) { for ( int i = p * 2 ; i <= MAX ; i += p ) prime [ i ] = true ; } } prefix [ 0 ] = prefix [ 1 ] = 0 ; for ( int p = 2 ; p <= MAX ; p ++ ) { prefix [ p ] = prefix [ p - 1 ] ; if ( prime [ p ] == false ) prefix [ p ] ++ ; } } static int query ( int L , int R ) { return prefix [ R ] - prefix [ L - 1 ] ; } public static void Main ( ) { buildPrefix ( ) ; int L = 5 , R = 10 ; Console . WriteLine ( query ( L , R ) ) ; L = 1 ; R = 10 ; Console . WriteLine ( query ( L , R ) ) ; } }