C # implementation of the approach
using System ; using System . Collections . Generic ; class GFG { static int limit = 1000000000 ; static int MAX_PRIME = 2000000 ; static int MAX = 1000000 ; static int I_MAX = 50000 ; static Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; static int [ ] b = new int [ MAX ] ; static int [ ] p = new int [ MAX ] ; static int j = 0 ; static bool [ ] prime = new bool [ MAX_PRIME + 1 ] ;