c - 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 只会浪费执行速度。相反，检查是否成功并跳出循环。

考虑到这些修改(并且您的代码清除了大量 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;
}