关于在线测评系统的一道问题

0

题目

给定多行,一行一个整数i,输出第i个素数(素数2是第1个素数),每个结果一行,最后一行有回车;直至输入结束

i<100010

例子

输入

1
2
5
3

输出

2
3
11
5

我的解答

#include<stdio.h>
#define N 100010
int prime(int n);
long int Pprime(long int i);

main()
{
	int count=0;
	long int i=0,j=0,a[NN]={0};
	for(i;i<N;i++)
	{
		scanf("%ld",&a[i]);count++;
	}

	for(i=0;i<count;i++)
		printf("%ld\n",Pprime(a[i]));
	printf("\n");
}

int prime(long int n)
{
	int i;
	if(n==0||n==1)return 0;
	if(n==2)return 1;
	for(i=2;i<n;i++)
	{
		if(n%i==0) return 0;
		else if(n!=i+1) continue;
		else return 1;
	}
}

long int Pprime(long int i)
{
	int counter=0;
	long int j;
	for(j=1;j<100000000;j++)
	{
		if(prime(j)==1)
		{counter++;}
		while(i==counter)
			return j;
	}
}

弱鸡的提问

怎么结束数组的输入且满足题干要求?

感谢大佬!

祝好

0

你这复杂度就错了

i 的范围是小于 100000 第 100000 个素数是 1299709,就算一百万,那你的复杂度为 1000000 * sqrt(1000000) (你的素数还没有根号优化 复杂度会更高),复制度为

o(n*sqrt(n)) 也就是计算机 算 i = 100000 ,要运行10钟, 所以肯定 timeout。

这题的正确解法是 欧拉线晒 求素数, 欧拉线晒的复杂度可以近似的看成 O(n)


输入结束 是: while(~scanf("%d", &a)){}

#include<bits/stdc++.h>
using namespace std;
const int N=1400000;
int prime[N],vis[N],top=1;

void Prime() // 欧拉线晒求素数
{
    for(int i=2;i<N;i++)
	{
        if(!vis[i])prime[top++]=i;
        for(int j=1;j<top&&prime[j]*i<N;j++)
		{
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}


int main()
{
    Prime();
    int i;
    while(~scanf("%d", &i))
	{
        printf("%d\n", prime[i]);
    }
}
ava
啦啦啦

2020-4-19

技术讨论社区