Queries for maximum difference between prime numbers in given ranges | Java 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 ; Driven Program
public class GFG { final static int MAX = 100005 ; static void precompute ( int prefix [ ] , int suffix [ ] ) { boolean prime [ ] = new boolean [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) { prime [ i ] = true ; } for ( int i = 2 ; i * i < MAX ; i ++ ) { if ( prime [ i ] ) { for ( int j = i * i ; j < MAX ; j += i ) { prime [ j ] = false ; } } } prefix [ 1 ] = 1 ; suffix [ MAX - 1 ] = ( int ) 1e9 + 7 ; for ( int i = 2 ; i < MAX ; i ++ ) { if ( prime [ i ] ) { prefix [ i ] = i ; } else { prefix [ i ] = prefix [ i - 1 ] ; } } for ( int i = MAX - 2 ; i > 1 ; i -- ) { if ( prime [ i ] ) { suffix [ i ] = i ; } else { suffix [ i ] = suffix [ i + 1 ] ; } } } static int query ( int prefix [ ] , int suffix [ ] , int L , int R ) { if ( prefix [ R ] < L suffix [ L ] > R ) { return 0 ; } else { return prefix [ R ] - suffix [ L ] ; } } public static void main ( String [ ] args ) { int q = 3 ; int L [ ] = { 2 , 2 , 24 } ; int R [ ] = { 5 , 2 , 28 } ; int prefix [ ] = new int [ MAX ] , suffix [ ] = new int [ MAX ] ; precompute ( prefix , suffix ) ; for ( int i = 0 ; i < q ; i ++ ) { System . out . println ( query ( prefix , suffix , L [ i ] , R [ i ] ) ) ; } } }