在处理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; 
}