xingchen_wzt @ 2024-06-29 11:34:40

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,q,k[1000005],v[n+5];cin>>n>>q;
    for(int i=1;i<=q;i++)cin>>k[i];
    for(int i=2;i<=n-1;i++){
        for(int j=2;j<=n-1;j++){
            if(i%j==0)break;
            v[i-1]={i};
        }
    }
    for(int i=1;i<=q;i++)cout<<v[k[i]];
}

by BJqxszx_zhuyukun @ 2024-06-29 11:36:13

超时了，要用欧拉筛

by xingchen_wzt @ 2024-06-29 11:40:00

是它，是它，就是它，我们的TTTLE.

by xingchen_wzt @ 2024-06-29 11:40:46

我知道我很菜（>^<）

by ToMaT @ 2024-06-29 12:10:18

bool b[100000001];
int a[20000001], cnt=0;
void pp(int n){
    for(int i=2; i<=n; i++){
        if(b[i]==0)
            a[++cnt] = i ;
        for(int j=1; j<=cnt&&i*a[j]<=n; j++){
            b[i*a[j]] = 1 ;
            if(i%a[j]==0)
                break;
        } 
    }
    return;
}

by ToMaT @ 2024-06-29 12:10:47

上面是欧拉筛

by ToMaT @ 2024-06-29 12:14:17

埃氏筛会重复筛： 如42会被2,3,7各筛掉1次， 30会被2,3,5各筛掉1次 导致时间复杂度增加

by ToMaT @ 2024-06-29 12:16:03

楼主代码是O(n^2), 欧拉筛是O(n). 不会超时

by ToMaT @ 2024-06-29 12:17:07

@xingchen_wzt

by xingchen_wzt @ 2024-06-29 14:32:02

shuanQ

by xingchen_wzt @ 2024-06-29 14:49:45

@BJqxszx_zhuyukun 已关