c - HackerRank 项目欧拉 #21 : Amicable numbers

Question

Here是问题陈述。

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a)=b and d(b)=a, where a≠b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 therefore d(220)=284. The proper divisors of 284 are 1, 2, 4, 71 and 142 so d(284)=220.

Evaluate the sum of all the amicable numbers under N.

这是我的暴力破解代码

#include <stdio.h>

long long int sum(long long int n)
{
    long long int i, sum=0;
    for(i=1;i<n;i++)
    {
        if(n%i==0)
            sum+=i;
    }
    return sum;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n;
        scanf("%lld",&n);
        long long int i,sum1=0;
        for(i=1;i<n;i++)
        {
            if(sum(sum(i))==i&&sum(i)!=i)
                sum1+=i;
        }
        printf("%lld\n",sum1);
    }
    return 0;
}

此代码有效，但速度很慢。因此，我实现了一个更快的算法。

该算法将找到其质因数的除数之和并将它们相乘。该算法的证明 here .这是代码。

#include <stdio.h>

long long int power(long long int x, long long int y)
{
    long long int i,a=1;
    for(i=1;i<=y;i++)
        a*=x;
    return a;
}

long long int sumOfPrimeDivisors(long long int p, long long int a)
{
    long long int x;
    x=(power(p,a+1)-1)/(p-1);
    return x;
}

long long int isPrime(long long int n)
{
    long long int i,flag=1;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

void primeDivisors(long long int n, long long int b[], int *k)
{
    long long int i;
    *k=0;
    for(i=2;i<n;i++)
    {
        if(n%i==0 && isPrime(i))
        {
        b[(*k)++]=i;
        }
    }
}

long long int primeDivisorCount(long long int n, long long int p)
{
    long long int count=0;
    while(n%p==0)
    {
        count++;
        n/=p;
    }
    return count;
}

long long int sum(long long int n)
{
    long long int ans=1,b[15];
    int k,i;

    primeDivisors(n,b,&k);

    for(i=0;i<k;i++)
        ans*=sumOfPrimeDivisors(b[i],primeDivisorCount(n,b[i]));

    return ans-n;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n;
        scanf("%lld",&n);

        printf("%lld %lld\n",sum(n),sum(sum(n)));
    }

    return 0;
}

这段代码给出了 n=220 (284 220) 的正确输出。但是当我用

替换 printf 时

long long int i;

        for(i=1;i<n;i++)
        {
            if(sum(sum(i))==i && sum(i)!=i )
                printf("%lld\n",i);
        }

我得到了输出的所有垃圾值。

例如，

Input

1
9949

Output

-9948

我做错了什么？

Answer 1

改变

if(sum(sum(i))==i && sum(i)!=i )

到

if(sum(sum(i))==i && sum(i)!=i && sum(i)>0)

帮助给出正确的输出。