c - c处理12位数字时的性能问题

目前我正在研究一个程序。程序运行正常，但存在性能问题。代码如下。

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

我在这里无法获得最大素数。
谁能告诉我我该怎么办？我花了太多时间才能快速获得输出？

最佳答案

如果您正在寻找最大质数，为什么要从2开始？从n开始检查并向后工作
calculate可以运行得更快，因为您只需要检查最大为sqrt(temp)的除数，如果它的除数大于该值，它的除数也小于该值。
循环增量和减量可以在2跳中完成。因此，您还可以将要检查的数字范围减半。
在搜索循环中间调用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;
}