全部TLE!!!

hkc101 @ 2024-05-15 19:42:26

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
bool ss(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}
int main(){
    int n,q;
    cin>>n>>q;
    int gs=1;
    for (int i=2;i<=n;i++){
        if(ss(i)){
            a[gs]=i;
            gs++;
        }
    }
    for (int i=1;i<=q;i++){
        int k;
        cin>>k;
        cout<<a[k];
    }
    return 0;
} 

by ZjfAKIOI @ 2024-05-15 19:48:35

算法不对

by ZjfAKIOI @ 2024-05-15 19:49:01

要用筛法，不是这么判断

by ZjfAKIOI @ 2024-05-15 19:49:40

#include<bits/stdc++.h>
using namespace std;
bool isprime[100000005];
int prime[100000005];
int main(){
    int q,n;
    cin>>n>>q;
    int tot=0;
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i<=n;i++){
        if(isprime[i]) prime[++tot]=i;
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
    while(q--){
        int k;
        cin>>k;
        cout<<prime[k]<<endl;
    }
    return 0;
}

by hkc101 @ 2024-05-15 19:52:22

厚礼蟹

by hkc101 @ 2024-05-15 19:53:37

我嘞个烧缸

by kevinZ99 @ 2024-05-15 19:57:41

@hkc101 请使用正确的欧拉筛，您真的没有算过时间吗？，你这是 \mathcal{O}(n \sqrt{n}) 的啊

#include <bits/stdc++.h>
using namespace std;
int prime_number[50000005];
bitset<100000005>prime_flag;
int ai=0;
void init_prime(){
    int N=1e8;
    prime_flag[0]=true;
    prime_flag[1]=true;
    prime_flag[2]=false;
    for(int i=2;i<=N;i++){
        if(!prime_flag[i])prime_number[ai++]=i;
        for(int j=0;j<ai&&i*prime_number[j]<=N;j++){
            prime_flag[i*prime_number[j]]=true;
            if(i%prime_number[j]==0)break;
        }
    }
}
int main(){
    init_prime();
    int n,k;
    scanf("%d%d",&n,&k);
    while(k--){
        int x;
        scanf("%d",&x);
        printf("%d\n",prime_number[x-1]);
    }
    return 0;
} 

by Ravener @ 2024-05-15 20:16:33

@kevinZ99
楼主用的是埃氏筛
时间复杂度应为 O(n \log \log n)
（之前我写 tj 就被这玩意坑惨了）

by shimucheng @ 2024-06-16 21:49:34

@hkc101 您看一下这时间复杂度，得用欧拉筛或埃氏筛才能过哦

by hkc101 @ 2024-06-27 22:35:18

大家好，我是小孩，不用您。