Queries for maximum difference between prime numbers in given ranges | PHP 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
< ? php $ MAX = 100005 ; function precompute ( & $ prefix , & $ suffix ) { global $ MAX ; $ prime = array_fill ( 0 , $ MAX , true ) ; for ( $ i = 2 ; $ i * $ i < $ MAX ; $ i ++ ) { if ( $ prime [ $ i ] ) { for ( $ j = $ i * $ i ; $ j < $ MAX ; $ j += $ i ) $ prime [ $ j ] = false ; } } $ prefix [ 1 ] = 1 ; $ suffix [ $ MAX - 1 ] = 1e9 + 7 ; for ( $ i = 2 ; $ i < $ MAX ; $ i ++ ) { if ( $ prime [ $ i ] ) $ prefix [ $ i ] = $ i ; else $ prefix [ $ i ] = $ prefix [ $ i - 1 ] ; } for ( $ i = $ MAX - 1 ; $ i > 1 ; $ i -- ) { if ( $ prime [ $ i ] ) $ suffix [ $ i ] = $ i ; else $ suffix [ $ i ] = $ suffix [ $ i + 1 ] ; } } function query ( $ prefix , $ suffix , $ L , $ R ) { if ( $ prefix [ $ R ] < $ L $ suffix [ $ L ] > $ R ) return 0 ; else return $ prefix [ $ R ] - $ suffix [ $ L ] ; } $ q = 3 ; $ L = array ( 2 , 2 , 24 ) ; $ R = array ( 5 , 2 , 28 ) ; $ prefix = array_fill ( 0 , $ MAX + 1 , 0 ) ; $ suffix = array_fill ( 0 , $ MAX + 1 , 0 ) ; precompute ( $ prefix , $ suffix ) ; for ( $ i = 0 ; $ i < $ q ; $ i ++ ) echo query ( $ prefix , $ suffix , $ L [ $ i ] , $ R [ $ i ] ) . " STRNEWLINE " ; ? >