王仁之2013 @ 2024-08-15 09:45:31
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int k,d;
scanf("%d %d",&k,&d);
int a[100000] = {0};
int count = 0;
for (int i = 2; i <= k; i++) {
if (isPrime(i)) {
a[count++] = i;
}
}
for (int i = 0; i < d; i++) {
int x;
scanf("%d",&x);
printf("%d\n",a[x-1]);
}
return 0;
}by realheizi @ 2024-08-15 10:00:15
不建议把数组开在主函数内
by realheizi @ 2024-08-15 10:02:06
@王仁之2013 你的做法疑似会超时，这个题用欧拉筛
by realheizi @ 2024-08-15 10:04:13
n<=1e8,你这个O（n sqrt（n））的复杂度不行
by realheizi @ 2024-08-15 10:05:53
建议去网上找个欧拉筛的讲解
by realheizi @ 2024-08-15 10:08:13
欧拉筛关键代码：
for(int i=2;i<=n;i++){
if(is_prime[i]){//如果i是质数
prime[len++]=i;//就应该存入表中
}
for(int k=1;k<len&&prime[k]*i<=n;k++){//但是无论是不是质数，都要与已有质数相乘
is_prime[prime[k]*i]=false;//筛掉得到的数
if(i%prime[k]==0) break; //如果当前质数已经是这个数的因数，退出循环
}
}