2

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

#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。

4

5 回答 5

3 
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 */

}
于 2013-09-29T15:33:56.180 回答
1

保持相同的逻辑，您可以通过仅执行循环直到 sqrt(num) 来减少时间。因为如果它不是素数，那么至少会有一个除数小于 sqrt(num)。

让我们假设 num 不是素数。所以对于一些 1< a < num，a*b = num。

所以 a 或 b 应该小于 sqrt(num)。

因此，您的 is_prime 代码应更改为如下代码

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

    return true;
}

现在如果你想改变你的逻辑，那么有一种称为筛法的算法可以找到所有小于给定数的素数。看看这个筛算法

于 2013-09-29T12:50:50.637 回答
1

main() 中的循环中的 if 语句应首先检查 n%i==0，以便不检查非因子的素数。在我在现代 Intel CPU 上运行的一个简单测试用例中，仅这一点就使程序在从 1 到 2000 的所有数字上的速度提高了 200 倍以上。下面的 mod 只是到 main() （我把它分解成一个返回最大素数的函数）显着提高了速度。我也认为数字本身是一个可能的因素（原文中没有这样做）。

unsigned long long largest_prime_factor(unsigned long long n)

    {
    unsigned long long i,sqrtn,maxprime;

    if (is_prime(n))
        return(n);
    sqrtn=(unsigned long long)sqrt((double)n);
    maxprime=1;
    for (i=2;i<=sqrtn;i++)
        {
        if (n%i==0)
            {
            unsigned long long f;

            f=n/i;
            if (is_prime(f))
                return(f);
            if (is_prime(i))
                maxprime=i;
            }
        }
    return(maxprime);
    }
于 2013-09-29T13:26:52.130 回答
1

玩得开心……一个函数适用于所有素因子，一个函数适用于最大素因子：

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

typedef unsigned long long u64_t;

static size_t prime_factors(u64_t value, u64_t *array)
{
    size_t n_factors = 0;
    u64_t n = value;
    u64_t i;

    while (n % 2 == 0)
    {
        n /= 2;
        //printf("Factor: %llu (n = %llu)\n", 2ULL, n);
        array[n_factors++] = 2;
    }

    while (n % 3 == 0)
    {
        n /= 3;
        //printf("Factor: %llu (n = %llu)\n", 3ULL, n);
        array[n_factors++] = 3;
    }

    for (i = 6; (i - 1) * (i - 1) <= n; i += 6)
    {   
        while (n % (i-1) == 0)
        {
            n /= (i-1);
            //printf("Factor: %llu (n = %llu)\n", (i-1), n);
            array[n_factors++] = (i-1);
        }
        while (n % (i+1) == 0)
        {
            n /= (i+1);
            //printf("Factor: %llu (n = %llu)\n", (i+1), n);
            array[n_factors++] = (i+1);
        }
    }
    if (n != 1)
        array[n_factors++] = n;

    return n_factors;
}

static u64_t max_prime_factor(u64_t value)
{
    u64_t n = value;
    u64_t i;
    u64_t max = n;

    while (n % 2 == 0)
    {
        n /= 2;
        //printf("Factor: %llu (n = %llu)\n", 2ULL, n);
        max = 2;
    }

    while (n % 3 == 0)
    {
        n /= 3;
        //printf("Factor: %llu (n = %llu)\n", 3ULL, n);
        max = 3;
    }

    for (i = 6; (i - 1) * (i - 1) <= n; i += 6)
    {   
        while (n % (i-1) == 0)
        {
            n /= (i-1);
            //printf("Factor: %llu (n = %llu)\n", (i-1), n);
            max = (i-1);
        }
        while (n % (i+1) == 0)
        {
            n /= (i+1);
            //printf("Factor: %llu (n = %llu)\n", (i+1), n);
            max = (i+1);
        }
    }
    //printf("Max Factor = %llu\n", (n == 1) ? max : n);

    return (n == 1) ? max : n;
}

static void print_factors(u64_t value, size_t n_factors, u64_t *factors)
{
    printf("%20llu:", value);
    int len = 21;
    for (size_t i = 0; i < n_factors; i++)
    {
        if (len == 0)
            len = printf("%.21s", "");
        len += printf(" %llu", factors[i]);
        if (len >= 60)
        {
            putchar('\n');
            len = 0;
        }
    }
    if (len > 0)
        putchar('\n');
}

void builtin_tests(void)
{
    u64_t tests[] =
    {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
        19, 20, 25, 49, 63, 69, 71, 73, 825, 829, 1000, 6857, 73112,
        731122, 7311229, 73112293, 731122935, 7311229357, 73112293571,
        600851475143, 731122935711, 7311229357111,
        18446744073709551610ULL, 18446744073709551611ULL,
        18446744073709551612ULL, 18446744073709551613ULL,
        18446744073709551614ULL, 18446744073709551615ULL,
    };
    u64_t factors[64];

    for (size_t i = 0; i < sizeof(tests)/sizeof(tests[0]); i++)
    {
        u64_t max = max_prime_factor(tests[i]);
        printf("%20llu -> Max Prime Factor = %llu\n", tests[i], max);
        size_t n_factors = prime_factors(tests[i], factors);
        print_factors(tests[i], n_factors, factors);
    }
}

int main(int argc, char **argv)
{
    if (argc == 1)
        builtin_tests();
    else
    {
        for (int i = 1; i < argc; i++)
        {
            u64_t factors[64];
            u64_t value = strtoull(argv[i], 0, 0);
            u64_t max = max_prime_factor(value);
            printf("%20llu -> Max Prime Factor = %llu\n", value, max);
            size_t n_factors = prime_factors(value, factors);
            print_factors(value, n_factors, factors);
        }
    }
    return 0;
}

结果

                   1 -> Max Prime Factor = 1
                   1:
                   2 -> Max Prime Factor = 2
                   2: 2
                   3 -> Max Prime Factor = 3
                   3: 3
                   4 -> Max Prime Factor = 2
                   4: 2 2
                   5 -> Max Prime Factor = 5
                   5: 5
                   6 -> Max Prime Factor = 3
                   6: 2 3
                   7 -> Max Prime Factor = 7
                   7: 7
                   8 -> Max Prime Factor = 2
                   8: 2 2 2
                   9 -> Max Prime Factor = 3
                   9: 3 3
                  10 -> Max Prime Factor = 5
                  10: 2 5
                  11 -> Max Prime Factor = 11
                  11: 11
                  12 -> Max Prime Factor = 3
                  12: 2 2 3
                  13 -> Max Prime Factor = 13
                  13: 13
                  14 -> Max Prime Factor = 7
                  14: 2 7
                  15 -> Max Prime Factor = 5
                  15: 3 5
                  16 -> Max Prime Factor = 2
                  16: 2 2 2 2
                  17 -> Max Prime Factor = 17
                  17: 17
                  18 -> Max Prime Factor = 3
                  18: 2 3 3
                  19 -> Max Prime Factor = 19
                  19: 19
                  20 -> Max Prime Factor = 5
                  20: 2 2 5
                  25 -> Max Prime Factor = 5
                  25: 5 5
                  49 -> Max Prime Factor = 7
                  49: 7 7
                  63 -> Max Prime Factor = 7
                  63: 3 3 7
                  69 -> Max Prime Factor = 23
                  69: 3 23
                  71 -> Max Prime Factor = 71
                  71: 71
                  73 -> Max Prime Factor = 73
                  73: 73
                 825 -> Max Prime Factor = 11
                 825: 3 5 5 11
                 829 -> Max Prime Factor = 829
                 829: 829
                1000 -> Max Prime Factor = 5
                1000: 2 2 2 5 5 5
                6857 -> Max Prime Factor = 6857
                6857: 6857
               73112 -> Max Prime Factor = 37
               73112: 2 2 2 13 19 37
              731122 -> Max Prime Factor = 52223
              731122: 2 7 52223
             7311229 -> Max Prime Factor = 24953
             7311229: 293 24953
            73112293 -> Max Prime Factor = 880871
            73112293: 83 880871
           731122935 -> Max Prime Factor = 89107
           731122935: 3 5 547 89107
          7311229357 -> Max Prime Factor = 7311229357
          7311229357: 7311229357
         73112293571 -> Max Prime Factor = 8058227
         73112293571: 43 211 8058227
        600851475143 -> Max Prime Factor = 6857
        600851475143: 71 839 1471 6857
        731122935711 -> Max Prime Factor = 4973625413
        731122935711: 3 7 7 4973625413
       7311229357111 -> Max Prime Factor = 12939061
       7311229357111: 547 1033 12939061
18446744073709551610 -> Max Prime Factor = 1504703107
18446744073709551610: 2 5 23 53301701 1504703107
18446744073709551611 -> Max Prime Factor = 287630261
18446744073709551611: 11 59 98818999 287630261
18446744073709551612 -> Max Prime Factor = 2147483647
18446744073709551612: 2 2 3 715827883 2147483647
18446744073709551613 -> Max Prime Factor = 364870227143809
18446744073709551613: 13 3889 364870227143809
18446744073709551614 -> Max Prime Factor = 649657
18446744073709551614: 2 7 7 73 127 337 92737 649657
18446744073709551615 -> Max Prime Factor = 6700417
18446744073709551615: 3 5 17 257 641 65537 6700417
于 2013-09-30T03:40:03.017 回答
0

最好从数字的平方根开始循环到 3，同样你可以跳过偶数。

这样你就可以在短时间内得到答案..

于 2013-09-30T06:13:59.613 回答