c - 找到第 10000 个素数

Question

这是我查找第 10000 个素数的代码，但它真的很慢，需要 7 秒才能计算。

#include <stdio.h>
#include <stdlib.h>

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

int main()
{
    int i=2,counter=0;
    while(1)
    {
        if(prime(i))
        counter++;
        if(counter==10000)
        break;
        i++;
    }
    printf("10000th prime number is: %d",i);
}

这是蛮力方法，所以这可能就是它如此慢的原因。 我认为问题可能在于它必须多次调用函数。那么您认为可以优化什么，或者最好为此找到一些数学公式。

Answer 1

您可以通过对 prime() 进行以下更改来大幅减少时间:

1. 停在sqrt(n)。
2. 从 i=3 开始，将 i 增加 2。

这是一个包含两个版本以及每个版本所花费的时间的程序。

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

int is_prime1 (int n)
{
    int i;
    for(i=2;i<n;i++)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}

void do_it1(int max)
{
   clock_t start = clock();
   clock_t end;

   int i=2,counter=0;
   while(1)
   {
      if(is_prime1(i))
         counter++;
      if(counter==max)
         break;
      i++;
   }
   end = clock();

   printf("%dth prime number is: %d\n", max, i);
   printf("Time taken: %lf\n", 1.0*(end-start)/CLOCKS_PER_SEC);
}

int is_prime2 (int n)
{
    int i;
    int stop = sqrt(n);
    for(i=3;i<=stop;i+=2)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}

void do_it2(int max)
{
   clock_t start = clock();
   clock_t end;

   int i=3,counter=1;
   while(1)
   {
      if(is_prime2(i))
         counter++;
      if(counter==max)
         break;
      i += 2;
   }
   end = clock();

   printf("%dth prime number is: %d\n", max, i);
   printf("Time taken: %lf\n", 1.0*(end-start)/CLOCKS_PER_SEC);
}

int main(int argc, char** argv)
{
   int max = atoi(argv[1]);
   do_it1(max);
   do_it2(max);
}

执行示例:

./test 10000

示例输出:

10000th prime number is: 104729
Time taken: 9.469000
10000th prime number is: 104729
Time taken: 0.078000