UVa 10852 - Less Prime

// UVa 10852 - Less Prime

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int oo[1];

int main() {
	memset(oo, 127, sizeof(oo));
	// sieve
	vector<int> prime;
	bool isprime[10001];
	memset(isprime, true, sizeof(isprime));
	prime.push_back(2);
	for (int i = 4; i <= 10000; i += 2)
		isprime[i] = false;
	for (int i = 3; i <= 10000; i++)
		if (isprime[i]) {
			for (int j = i * i; j <= 10000; j += (i << 1))
				isprime[j] = false;
			prime.push_back(i);
		}
	// main
	int t;
	for (cin >> t; t; t--) {
		// input
		int n;
		cin >> n;
		// solve
		int sol = oo[0], s;
		for (int i = 0; i < prime.size() && prime[i] <= n; i++) {
			int x = prime[i];
			int p = n / x;
			if (p * x < sol) {
				sol = p * x;
				s = x;
			}
		}
		cout << s << endl;
	}

	return 0;
}