primesieve.cpp

#include <bitset>
#include <cmath>
#include <vector>
#include <iostream>
 
using namespace std;
 
const int MAX_PRIMES=100000000;   // Note the problem bounds (up to 10^8)
//vector<int> primes;             // Note the restrictive memory limit: 50MB is probably too small for all the primes!
                                  // 4 bytes/int * 5761455 primes ~ 22 MB alone!
 
 
bitset<MAX_PRIMES> nums;          // true for each prime
vector<int> primes;               // list of primes
 
 
void sieve(int n) {               // eratosthenes as a drop-in solution
  nums.set();                     // set all values to true
  nums[0] = nums[1] = false;
  for(int i=2; i<=sqrt(n)+1; i++) // filter out non-primes
    if(nums[i])
      for(int j=i*i; j<n+2; j+=i)   
    nums[j] = false;
}  
 
int main() {
  int n, q, x, total=0;
 
  cin >> n >> q;           // read initial values
  sieve(n);                // calculate prime flags (only)
 
  for(int i=2; i<=n; i++)  // count primes in range
    if(nums[i])
      total++;
 
  cout << total << endl;   // print value
 
  for(int i=0; i<q; i++) { // query, print results from flags
    cin >> x;
    if(nums[x])
      cout << "1" << endl;
    else
      cout << "0" << endl;
  }
 
  return 0;
}

The title of the problem is a strong hint towards its intent to educate the reader about Prime Sieves. Python3 can be immediately ruled out as a likely solution due to the problem bounds. Note that you need to compute 1 ≤ n ≤ 10⁸ primes in the worst case (and that they will definitely test this upper bound!).

The second thing thing that we can most likely rule out is the storage of each prime. Note that the problem doesn't require printing primes themselves, only identifying primes.