Count Primes in Ranges | PHP 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 value in prime [ i ] will " prime [ 0 . . n ] " . A 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 $prefix [ 0 ] = $prefix [ 1 ] = 0 ; ; Returns count of primes in range from L to R ( both inclusive ) . ; Driver code
< ? php $ MAX = 10000 ; $ prefix = array_fill ( 0 , ( $ MAX + 1 ) , 0 ) ; function buildPrefix ( ) { global $ MAX , $ prefix ; $ prime = array_fill ( 0 , ( $ MAX + 1 ) , true ) ; for ( $ p = 2 ; $ p * $ p <= $ MAX ; $ p ++ ) { if ( $ prime [ $ p ] == true ) { for ( $ i = $ p * 2 ; $ i <= $ MAX ; $ i += $ p ) $ prime [ $ i ] = false ; } } for ( $ p = 2 ; $ p <= $ MAX ; $ p ++ ) { $ prefix [ $ p ] = $ prefix [ $ p - 1 ] ; if ( $ prime [ $ p ] ) $ prefix [ $ p ] ++ ; } } function query ( $ L , $ R ) { global $ prefix ; return $ prefix [ $ R ] - $ prefix [ $ L - 1 ] ; } buildPrefix ( ) ; $ L = 5 ; $ R = 10 ; echo query ( $ L , $ R ) . " STRNEWLINE " ; $ L = 1 ; $ R = 10 ; echo query ( $ L , $ R ) . " STRNEWLINE " ; ? >