C ++ implementation of the approach
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define limit  1000000000 NEW_LINE #define MAX_PRIME  2000000 NEW_LINE #define MAX  1000000 NEW_LINE #define I_MAX  50000 NEW_LINE map < int , int > mp ; int b [ MAX ] ; int p [ MAX ] ; int j = 0 ; bool prime [ MAX_PRIME + 1 ] ;