0

我有一个 C 代码可以在下面找到大的完美数字，

#include <stdio.h>

int main ()
{
    unsigned long long num,i,sum;

    while (scanf ("%llu",&num) != EOF && num)
    {
        sum = 1;

        for (i=2; i*i<=num; i++)
        {
            if (num % i == 0)
            {
                if (i*i == num)
                    sum += i;
                else
                    sum += (i + num/i);
            }
        }

        if (sum == num)
            printf ("Perfect\n");
        else if (sum > num)
            printf ("Abundant\n");
        else
            printf ("Deficient\n");
    }

    return 0;
}

我试图找出一个数字是完美的、丰富的还是不足的。我运行一个直到平方根的循环num以最小化运行时间。它工作正常<= 10^15，但对于较大的值，执行时间太长。

例如，对于以下输入集，

8
6
18
1000000
1000000000000000
0

此代码显示以下输出，

Deficient
Perfect
Abundant
Abundant
Abundant

但是，对于 10^16，它不会快速响应。

那么，有没有更好的方法来为过长的值找到一个完美的数字？或者有什么更好的算法可以在这里实现？？？:)

4

3 回答 3

2

是的，有更好的算法。

你的算法基本上是一个简单的算法 - 将一个数字的除数相加以找到......一个数字的除数之和（不包括它自己）。但是你可以使用数论公式来求一个数（包括它自己）的除数之和。如果除以的素数n是p1, p2, ...,pk并且这些素数在 的规范分解中的幂n是a1, a2, ..., ak, 那么 的除数之和n是

(p1**(a1+1) - 1) / (p1 - 1) * (p2**(a2+1) - 1) / (p2 - 1) * ...
    * (pk**(ak+1) - 1) / (pk - 1)

与找到 的所有除数相比，您可以更快地找到主要除数及其指数n。从上面的表达式中减去n，你得到你想要的总和。

当然，有一些技巧可以更有效地找到pis 和ais：我将把它留给你。

顺便说一句，如果你的目的只是为了找到完美的数字，就像你的标题一样，你最好使用欧几里德的偶数素数公式。通过检查所有2**p-1素数p以查看它们是否为素数来找到梅森素数 - 也有这样做的捷径 - 然后从该梅森素数构造一个完美数。不过，这会遗漏任何奇数完美数。如果你找到任何东西，让数学界知道——那会让你世界闻名。

当然，找到完美数字的最快方法是使用已经由其中一些组成的列表。

于 2017-06-20T16:51:41.450 回答
1 
// Program to determine whether perfect or not

# include <bits/stdc++.h>
using namespace std;

map<long long int, int> mp;    // to store prime factors and there frequency

void primeFactors(long long int n)
{
// counting the number of 2s that divide n
while (n%2 == 0)
{
    mp[2] = mp[2]+1;
    n = n/2;
}

long long int root = sqrt(n);
// n must be odd at this point.  So we can skip every even numbers next
for (long long int i = 3; i <= root; i = i+2)
{
    // While i divides n, count frequency of i prime factor and divide n
    while (n%i == 0)
    {
        mp[i] = mp[i]+1;
        n = n/i;
    }
}

// This condition is to handle the case whien n is a prime number
    // greater than 2
    if (n > 2)
    {
        mp[n] = mp[n]+1;
    }
}

long long int pow(long long int base, long long int exp)
{
    long long int result = 1;
    base = base;
    while (exp>0)
    {
        if (exp & 1)
            result = (result*base);
        exp >>= 1;
        base = (base*base);
    }
    return result;
}

int main ()
{
    long long num, p, a, sum;

    while (scanf ("%lld",&num) != EOF && num)
    {
        primeFactors(num);
        sum = 1;

        map<long long int, int> :: iterator i;
        for(i=mp.begin(); i!=mp.end(); i++)
        {
            p = i->first;
            a = i->second;
            sum = sum*((pow(p,a+1)-1)/(p-1));
        }

        if (sum == 2*num)
            printf ("Perfect\n");
        else if (sum > num)
            printf ("Abundant\n");
        else
            printf ("Deficient\n");

        mp.clear();
    }

    return 0;
}
于 2017-07-11T23:50:39.723 回答
1

这是一个数字因式分解的问题。您可以在此处阅读更多信息：https ://en.wikipedia.org/wiki/Integer_factorization

不幸的是，对您来说没有好消息 - 数字越大，花费的时间就越长。

从您的代码开始，尽量不要将i*i每次迭代相乘。而不是： for (i=2; i*i<=num; i++)

先计算 num 的平方根，然后比较 i <= square_root_of_num in the loop。

于 2017-06-20T16:52:28.603 回答