c - 查找质数 10001 优化问题

Question

所以我创建了一个程序来查找第 10,001 个素数。这是该程序的主要部分:

int main(){

  int i;
  int j;
  int count=0;
  int currnumber=0;

  for(i=1; count < 10002; i++){

      if(isPrime(i)){

          count++;
          currnumber = i;

          if(count == 10002)
              printf("%i",currnumber);
      }


  }

}

下面是我在自定义库中构建的 IsPrime 函数的代码:

long long isPrime(long long number){

    long long i = 2;

    if(number == 2)
        return 1;

    for(i=2;i<number;i++){

        if(number % i == 0)
            return 0;



    }
    if(i >= number && ((number % 1 == 0) && (number % number == 0)))
        return 1;
}

当我运行程序时，它运行并给出了正确答案(这是一个欧拉问题，所以我知道我做对了 :D)，但它至少需要 6 秒来处理。所以我的问题是:

1. 为什么要花这么长时间？这与我设置算法的方式有关吗？
2. 我怎样才能改进我的代码以使其运行得更快？

提前致谢!

Answer 1

您可以做的第一件事可能是缓存您创建的质数值，并使用 sieve of eratosthenes算法，以便在找到质数值后不必不断地重新计算它们。