Sieve of Eratosthenes
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 ;