Проблема с производительностью в c, имея дело с 12-значным номером

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 в середине цикла поиска, когда проверка завершилась неудачей, является просто пустой тратой времени выполнения. Вместо этого проверьте успех и выйдите из цикла.

С этими изменениями в виду (и код очищаемых от многих УБ):

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