查找10000th素數

Question

這是我的代碼，用於查找10000th素數，但它非常慢，需要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 

Answer 2

要優化你的代碼一點點的變化（基於意見中提出）：

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

Answer 3

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

int *prime; 
int prime_n; 

void make_prime_table(int n){ 
    prime = malloc(sizeof(int) * n/2); 
    prime_n =0; 
    prime[prime_n++] = 2; 
    prime[prime_n++] = 3; 
    int i, j; 
    for(i = 5; i <= n; i +=2){ 
     bool is_prime = true; 
     for(j = 1; j < prime_n ; ++j){ 
      int t = prime[j]; 
      if(t * t > i) 
       break; 
      if(i % t == 0){ 
       is_prime = false; 
       break; 
      } 
     } 
     if(is_prime) 
      prime[prime_n++] = i; 
    } 
} 

int main(void){ 
    int n = 105000; 
    make_prime_table(n); 
    if(prime_n >= 10000) 
     printf("10000th prime number is: %d\n", prime[9999]); 

    free(prime); 
    return 0; 
}