Count Primes in Ranges | Python3 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
MAX = 10000 NEW_LINE prefix = [ 0 ] * ( MAX + 1 ) NEW_LINE def buildPrefix ( ) : NEW_LINE INDENT prime = [ 1 ] * ( MAX + 1 ) NEW_LINE p = 2 NEW_LINE while ( p * p <= MAX ) : NEW_LINE INDENT if ( prime [ p ] == 1 ) : NEW_LINE INDENT i = p * 2 NEW_LINE while ( i <= MAX ) : NEW_LINE INDENT prime [ i ] = 0 NEW_LINE i += p NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for p in range ( 2 , MAX + 1 ) : NEW_LINE INDENT prefix [ p ] = prefix [ p - 1 ] NEW_LINE if ( prime [ p ] == 1 ) : NEW_LINE INDENT prefix [ p ] += 1 NEW_LINE DEDENT DEDENT DEDENT def query ( L , R ) : NEW_LINE INDENT return prefix [ R ] - prefix [ L - 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT buildPrefix ( ) NEW_LINE L = 5 NEW_LINE R = 10 NEW_LINE print ( query ( L , R ) ) NEW_LINE L = 1 NEW_LINE R = 10 NEW_LINE print ( query ( L , R ) ) NEW_LINE DEDENT