线性筛题求助大佬,只能通过一个。3383

回复帖子

@AleaxanderXuan 2021-09-15 13:39 回复

题目:
题目描述: 如题,给定一个范围n,有q个询问,每次输出第k小的素数。

输入格式: 第一行包含两个正整数 n,q分别表示查询的范围和查询的个数。

接下来q行每行一个正整数k,表示查询第k小的素数。

输出格式 输出q行,每行一个正整数表示答案。

输入输出样例: 输入:

100 5

1

2

3

4

5

输出:

2

3

5

7

11 时间:2s 内存:512mb

#include<stdio.h>
int n,q,cnt;
//筛素数的范围(2-n),查寻个数,素数的个数 
int k[1000000];
//用来装每个查询的数 
bool check[100000000];
//线行筛检查合数 
int ss[100000000];
//用来装筛出来的素数 
int main(){
    scanf("%d %d",&n,&q);
    for(int i=0;i<q;i++){
        scanf("%d",&k[i]);
    }
    for(int i=2;i<n;i++){
        if(!check[i]){
            ss[cnt++]=i;
        }
        for(int j=0;j<cnt&&i*ss[j]<=n;j++){
            check[i*ss[j]]=true;
            if(i%ss[j]==0) break; 
        }
    }
    for(int i=0;i<q;i++){
        printf ("%d\n",ss[k[i]-1]);
    }
    return 0;
}

只能过一个,时间,空间都没有问题。

求助大佬

题目:3383

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。