求第K大的素数
如题

k=1 输出 2
k=2 输出 3

1=<k<=10000

时间限制 ：1S


我的算法（不过好像有点超时。。。）

C/C++ code

#include <iostream>using namespace std;long f(int *A,int k){    if (k==1)    {        return 2;    }    A[0]=2;    int i=3;    int index;    for (;A[k-1]==0;i+=2)    {        for (index=0;A[index]!=0;++index)        {            if (i%A[index]==0)            {                break;            }        }        if (A[index]==0)        {            A[index]=i;        }    }    return A[k-1];}int main(){    int n=10000;    int *A=new int[n];    for (int i=0;i<=n-1;++i)    {        A[i]=0;    }    int k;    cin>>k;    cout<<f(A,k);    system("pause");    return 0;}

[解决办法]
确实可以这样判断,求素数可以用筛法,会比这样挨个验证快很多!

可以根据素数的密度,大概估计一个上限,然后用筛法求就行了.

C# code

        private int[] GetPrimeList(int upperValue)        {            List<int> PrimeList = new List<int>();            bool[] flags = new bool[upperValue + 2];            for (int i = 2; i <= (int)Math.Sqrt(upperValue); i++)            {                if (!flags[i])                {                    for (int j = i * i; j <= upperValue; j += i)                    {                        flags[j] = true;                    }                }            }            for (int i = 2; i < upperValue; i++)            {                if (!flags[i])                {                    PrimeList.Add(i);                }            }            return PrimeList.ToArray();        }
[解决办法]
探讨

其实这个问题以前讨论过很多遍了,筛法的效率应当是被公认的。 

我也做过一些测试： 

如果用奇数试除的话，求1,000,000以内的所有质数，大概需要运算65,000,000次 
如果用已经求出来的质数试除的话，求1,000,000以内的所有质数，大概需要运算14,000,000次 
如果用最普通的Eratosthenes筛法的话，求1,000,000以内的所有质数，大概需要运算2,500,000次 

[解决办法]
探讨

to:阿诺 

mathematics用的是什么方法你可以写出来,我也顺便学习一下,如果不用算前面的可以直接推出第K个素数, 
那么对这道题就很有意义,如果不能直接推出,哪怕可以少算很大一部分中间的素数,也是有意义的。 
如果仍然要一个一个算的话，那意义就不大了，复杂度没什么本质变化。 

to：sp1234 

你给出的方法也是逐个验证的，虽然可以利用一下已经算出的结果，但本质上要算出第K个素数， 
仍然要将前K-1个算出来，使用筛…