9-27蚂蚁笔试
第二题：给定一个数x，有两种操作1: 减一和2: 除以一个素数。1操作只能在2操作前面。
十亿以内最大的素数间隔不超过300，知道这个的话这题应该不难
#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';
}
} 
影石Insta360公司氛围 452人发布