首页 > 代码库 > 九度OJ 1040 Prime Number (筛素数,试除法)

九度OJ 1040 Prime Number (筛素数,试除法)

题目描述:

Output the k-th prime number.

输入:

k≤10000

输出:

The k-th prime number.

样例输入:
3
7
样例输出:
5
17
这道题,好久以前使用试除法做的,原理是维护一个素数表,根据输入的num,确定是否之前算过,算过了,就直接输出,没算过,就现在开始算,并且把中间的素数全保存下来:

#include<stdio.h>
int k[10001];
int main(int argc, char *argv[])
{
    k[1]=2;
    int index=1;
    int i,j;
    int num;
    int tmp;
    while(scanf("%d",&num)!=EOF)
    {
        if(index>=num)
            printf("%d\n",k[num]);
        else
        {
            for(i=index+1;i<=num;++i)
            {
                tmp=k[i-1]+1;
                while(1){
                    for(j=1;j<=index;++j)
                    {
                        if(tmp%k[j]==0)
                            break;
                    }
                    if(j<=index)
                        tmp++;
                    else
                    {
                        k[i]=tmp;
                        index++;
                        break;
                    }
                }
            }
            printf("%d\n",k[num]);
        }
    }
    return 0;
}
今天本来想用筛选法做的,可是老错老错,后来才发现致命错误!!!(查了下,第10000个素数是接近30000的一个数,而我的筛选数组才10000大小。。。)

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
#define M 1000010
bool flag[M];
int prime[M];
void getprime()
{
    int cnt=1;
    for(int i=2;i<M;++i)
    {
        if(!flag[i])
        {
            prime[cnt++]=i;
            for(int j=i;j<M;j+=i)
                flag[j]=true;
        }
    }
}
int main(int argc, char *argv[])
{
    int k;
    // freopen("1040.in","r",stdin);
    getprime();
    prime[0]=0;
    while(scanf("%d",&k)!=EOF)
    {
        printf("%d\n",prime[k]);
    }
    return 0;
}

更喜欢筛选法,简单明了,而且还快

对比下测试结果——

试选法:


筛选法:


九度OJ 1040 Prime Number (筛素数,试除法)