找到第10000素数 [英] Find 10000th prime number

问题描述

这是我的code寻找第10000素数，但它实在是太慢了，需要7秒来计算。

This is my code for finding 10000th prime number but it is really slow, it takes 7 seconds to calculate.

#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);
}

这是蛮力方法，这样可能是原因，它是如此缓慢。
我想，可能是问题，它必须调用函数这么多次。那么你认为有什么可以对它进行优化，或最好是找一些这方面的数学公式。

It is brute force method so that's probably reason why it's so slow. I think problem may be that it has to call function so many times. So what do you think can it be optimised or it's better to find some math formula for this.

推荐答案

您可以充分通过了如下修改时间减少黄金（）：

You can reduce the time substantially by making the following changes to prime():

1. 在停止开方（N）。


2. 在 I = 3 启动和递增 I 按 2 。

1. Stopping at sqrt(n).
2. Starting at i=3, and incrementing i by 2.

下面是一个包含两个版本以及每个所花费的时间计划。

Here's a program that contains both versions and the time taken by each.

#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

这篇关于找到第10000素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！