#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;
}