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
 
# Implemented from Wikipedia
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 total number of primes
 
  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. Indeed, we could run our Sieve of Eratosthenes to see that there are 5761455 primes * 4 bytes per prime = 23045820 bytes required (or 21.978 MB) required for storage.²⁾ Although the bitsets is more space efficient than a vector of bools, we only have 50MB to work with. Since the vector of primes is not key to the sieve, we simply eliminate it (which will also speed up our processing).

Once we understand the bounds of the problem, processing the needed values is mostly done by parsing the bitset that results from the sieve, either to count the primes in our range or to query the primality of inputs in a loop.