Java implementation of the approach
import java . util . * ; class GFG { static int limit = 1000000000 ; static int MAX_PRIME = 2000000 ; static int MAX = 1000000 ; static int I_MAX = 50000 ; static HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; static int [ ] b = new int [ MAX ] ; static int [ ] p = new int [ MAX ] ; static int j = 0 ; static boolean [ ] prime = new boolean [ MAX_PRIME + 1 ] ;