# ZeroJudge - f803: 質數篩法練習
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f803
###### tags: `ZeroJudge` `數學` `質數` `二分搜尋法（Binary Search）`

#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 10000000

int primes[SIZE / 15], primeAmount;
bool notPrime[SIZE] = { true, true };

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i]) {
			primes[primeAmount] = i;
			++primeAmount;
		}
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	Initialize();
	int upperbound, numbers, target;
	cin >> upperbound >> numbers;
	while (numbers--) {
		cin >> target;
		cout << int(lower_bound(primes, primes + primeAmount, target) - primes) + 1 << '\n';
	}
}