9-27蚂蚁笔试

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 1e9 + 5;
// 素数筛法
vector<int> calprime(int n) {
	bool flag[n+1];
	memset(flag,0,sizeof(flag));
	vector<int> prime;
	int cnt = 0;//素数个数
	for(int i=2;i<n;i++) {
		if(!flag[i]) {
			prime.push_back(i);//将i加入素数表
			cnt++; 
		}
		for(int j=0;j<cnt;j++) {
			if(i * prime[j] > n) break;
			flag[i * prime[j]] = 1;
			if(i % prime[j]==0) break;
		}
	}
	return prime;
}
int cal(vector<int>& ve, int x) {
    int len = ve.size();
    int ans = 0;
    for (int i = 0; i < len && x >= ve[i]; ++i) {
        while (x % ve[i] == 0) {
            x /= ve[i];
            ans += 1;
        }
    }
    if (x > 1) ans += 1;
    return ans;
}
int main() {
    vector<int> ve = calprime(int(sqrt(maxn)));
    int T; cin >> T;
    // 十亿以内素数最大间隔为282
    int delta = 1000;
    while (T--) {
        int ans = maxn;
        int n; cin >> n;
        for (int i = 0; i < delta && n - i >= 0; ++i) {
            ans = min(ans, i + cal(ve, n - i));
        }
        cout << ans << '\n';
    }
}