Problem 7

10001番目の素数を求めます。

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。
10001 番目の素数を求めよ。

Problem 7 - PukiWiki

力技で順番に数えていきました。

#include <stdio.h>
#include <math.h>

#define PRIME_ORDER 10001

int is_prime(int num) {
    int i;
    int check_max = (int)floor(sqrt(num));

    for (i=2; i<=check_max; i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

void problem007()
{
    int ans;
    int num, pcount;

    /* solve this problem here */
    num = 1;
    pcount = 0;
    while (pcount < PRIME_ORDER) {
        num++;
        if (is_prime(num) > 0) {
            pcount++;
        }
    }
    ans = num;

    printf("%s: answer = %d\n", __FUNCTION__, ans);
}

int main(int argc, char* argv[]) 
{
    problem007();
    return 0;
}

実行結果

$ ./problem007
problem007: answer = 104743

ちゃんとエラトステネスの篩を使ってないから時間かかるかと思っていたけど一瞬だった。