在處理12位數字時c中的性能問題

Question

當前我正在開發一個程序。程序工作完美，但它有性能問題。代碼如下。

#include<stdio.h> 
int calculate(int temp) 
{ 
    int flag = 0,i = 2,tmp = 0; 
    for(i = 2;i < temp;i++) 
    { 
     if(temp % i == 0) 
     { 
      return 1; 
     } 
    } 
} 
int main() 
{ 
    long int i = 2,j,count = 0,n = 600851475143,flag = 0,prime = 0; 
    long int check; 
    while(i < n) 
    { 
     if(n % i == 0) 
     { 
      check = calculate(i); 
      if(check != 1) 
      { 
       prime = i; 
       printf(" Prime number is : %ld \n", prime); 
      } 
     } 
     i++; 
    } 
    printf(" Max prime number of %ld is : %ld \n",n,prime); 
    return 0; 
} 

我無法在此處獲得最大質數。 任何人都可以告訴我我應該做什麼需要太多時間我該怎麼做才能快速獲得輸出？

Answer 1

1. 如果你正在尋找一個最大黃金，爲什麼你開始2？在開始檢查n和向後

2. calculate工作可以跑得更快，因爲你只需要檢查除數高達sqrt(temp)，如果它有一個除數比大，它也有一個除數小於。

3. 你的循環增量和減量可以在2跳中完成。所以你也可以減半數字來檢查。

4. 在搜索循環的中間調用printf以便檢查失敗時只是浪費執行速度。相反，檢查成功並跳出循環。

考慮到這些修改（和你的代碼從很多UB的清洗）：

#include<stdio.h> 
int calculate(long int temp) 
{ 
    long int flag = 0,i = 2,tmp = 0; 

    if (temp % 2 == 0) 
     return 1; 

    for(i = 3; i*i <= temp; i+=2) 
    { 
     if(temp % i == 0) 
     { 
      return 1; 
     } 
    } 
    return 0; 
} 

int main(void) 
{ 
    long int j, count = 0, n = 600851475143, i = n, flag = 0, prime = 0; 
    long int check; 
    while(i > 0) 
    { 
     if(n % i == 0) 
     { 
      check = calculate(i); 
      if(check) 
      { 
       prime = i; 
       break; 
      } 
     } 
     i-=2; 
    } 
    printf(" Max prime number of %ld is : %ld \n",n,prime); 
    return 0; 
}