最后一个质数
2025-07-27 08:55:40
发布于：上海
7阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N];
// 质数判断函数
bool is_prime(int x) {
if (x < 2) return false;
if(x==0)return true;
for (long long i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
// 二分答案求上界
int upper_answer(int l, int r) {
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (is_prime(a[mid])) {
ans = mid; // 记录有效位置
l = mid + 1; // 尝试寻找更右边的质数
}
else {
r = mid - 1; // 非质数区域需向左收缩
}
}
return ans;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << upper_answer(1, n);
return 0;
}
这里空空如也
有帮助，赞一个