C-给定数的最大质因数

Question

我编写了以下代码来计算所提供数字的最大质因数通过标准输入但它需要很长时间才能执行。我怎样才能减少程序的执行时间？

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool is_prime(unsigned long long num)
{
    if (num == 0 || num == 1)
        return false;
    if (num == 2)
        return true;
    for (unsigned long long j = 2; j < num; j++)
        if(num%j==0)
            return false;

    return true;
}

int main(void)
{
    unsigned long long n,i;
    printf("enter the number: ");
    scanf("%llu",&n);
    for(i=n-1;i>1;i--)
        if((is_prime(i)) && n%i==0)
            break;
    printf("%llu\n",i);

    return 0;
}

输入的数字是 600851475143。

Answer 1

bool is_prime(unsigned long long num)
{
    if (num <  2) return false;      /* Reject border cases */

    if (num == 2) return true;       /* Accept the largest even prime */

    if ((num & (~1)) == num) return false;  /* Reject all other evens */

    unsigned long long limit = sqrt(num) + 1;  /* Limit the range of the search */

    for (unsigned long long j = 3; j < limit; j += 2)  /* Loop through odds only */
        if(num % j==0)
            return false;           /* Reject factors */

    return true;                    /* No factors, hence it is prime */

}