Queries for maximum difference between prime numbers in given ranges | Python 3 program to find maximum differences between two prime numbers in given ranges ; Precompute Sieve , Prefix array , Suffix array ; Sieve of Eratosthenes ; Precomputing Prefix array . ; Precompute Suffix array . ; Function to solve each query ; Driver Code
from math import sqrt NEW_LINE MAX = 100005 NEW_LINE def precompute ( prefix , suffix ) : NEW_LINE INDENT prime = [ True for i in range ( MAX ) ] NEW_LINE k = int ( sqrt ( MAX ) ) NEW_LINE for i in range ( 2 , k , 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT for j in range ( i * i , MAX , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT prefix [ 1 ] = 1 NEW_LINE suffix [ MAX - 1 ] = int ( 1e9 + 7 ) NEW_LINE for i in range ( 2 , MAX , 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT prefix [ i ] = i NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] NEW_LINE DEDENT DEDENT i = MAX - 2 NEW_LINE while ( i > 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT suffix [ i ] = i NEW_LINE DEDENT else : NEW_LINE INDENT suffix [ i ] = suffix [ i + 1 ] NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT DEDENT def query ( prefix , suffix , L , R ) : NEW_LINE INDENT if ( prefix [ R ] < L or suffix [ L ] > R ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return prefix [ R ] - suffix [ L ] NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT q = 3 NEW_LINE L = [ 2 , 2 , 24 ] NEW_LINE R = [ 5 , 2 , 28 ] NEW_LINE prefix = [ 0 for i in range ( MAX ) ] NEW_LINE suffix = [ 0 for i in range ( MAX ) ] NEW_LINE precompute ( prefix , suffix ) NEW_LINE for i in range ( 0 , q , 1 ) : NEW_LINE INDENT print ( query ( prefix , suffix , L [ i ] , R [ i ] ) ) NEW_LINE DEDENT DEDENT