九度OJ 1040：Prime Number（質數） （遞歸）

時間限制：1 秒

記憶體限制：32 兆

特殊判題：否

送出：5278

解決：2180

題目描述：

Output the k-th prime number.

輸入：

k≤10000

輸出：

The k-th prime number.

樣例輸入：

3
7      

樣例輸出：

5
17      

來源：

2008年上海交通大學計算機研究所學生機試真題

思路：

求質數要注意時間複雜度，隻需要搜到sqrt(n)即可判斷是否為質數。

另外如果多次求解，可以預先存數組，這樣避免多次求解。

代碼：

#include <stdio.h>
#include <math.h>
 
int isprime(int n)
{
    for (int i=2; i<=sqrt(n); i++)
    {
        if (n%i == 0)
            return 0;
    }
    return 1;
}
 
int kthprime(int k)
{
    int n = 1;
    while (k--)
    {
        n++;
        while (! isprime(n))
            n++;
    }
    return n;
}
 
int main(void)
{
    int k;
 
    while (scanf("%d", &k) != EOF)
    {
        printf("%d\n", kthprime(k));
    }
 
    return 0;
}
/**************************************************************
    Problem: 1040
    User: liangrx06
    Language: C
    Result: Accepted
    Time:70 ms
    Memory:928 kb
****************************************************************/