Queries for maximum difference between prime numbers in given ranges | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100005 NEW_LINE bool prime [ MAX ] ; int prefix [ MAX ] , suffix [ MAX ] ; void precompute ( int prefix [ ] , int suffix [ ] ) { memset ( prime , true , sizeof ( prime ) ) ; 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 ] = 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 - 1 ; i > 1 ; i -- ) { if ( prime [ i ] ) suffix [ i ] = i ; else suffix [ i ] = suffix [ i + 1 ] ; } } 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 ] ; } int main ( ) { int q = 3 ; int L [ ] = { 2 , 2 , 24 } ; int R [ ] = { 5 , 2 , 28 } ; precompute ( prefix , suffix ) ; for ( int i = 0 ; i < q ; i ++ ) cout << query ( prefix , suffix , L [ i ] , R [ i ] ) << endl ; return 0 ; }