Java implementation of above approach
import java . util . * ; public class Main { static class pair { public int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int MAX = 105 , q = 0 ; static int [ ] prime = new int [ MAX ] ; static void sieve ( ) { for ( int i = 2 ; i * i < MAX ; i ++ ) { if ( prime [ i ] == 0 ) { for ( int j = i * i ; j < MAX ; j += i ) prime [ j ] = 1 ; } } }