所有适当除数的总和

Question

我已经解决了一个问题:
给定一个自然数n(1 <= n <= 500000),请输出所有适当除数的总和.

定义:自然数的适当除数是严格小于数的除数.

例如,数字20有5个适当的除数:1,2,4,5,10,除数求和为:1 + 2 + 4 + 5 + 10 = 22.

输入

一个整数,表示测试用例的数量(大约等于200000),后面跟着许多行,每个行包含1到500000之间的一个整数.

产量

每行一个整数:分别给出的整数的除数和.

例

样本输入:

3
2
10
20

样本输出:

1
8
22

我的代码如下:

/* @BEGIN_OF_SOURCE_CODE */

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

    int main(int argc, const char * argv[])
    {
        int sum = 0,
        cases = 0,
        i, j, buff;

        scanf("%d", &cases); //Number of tests


        int *n;
        n = (int*) malloc(cases * sizeof(int)); //Defining array for numbers to be tested///////

        for (i = 0; i < cases; i++) {
            scanf("%d", &n[i]);
        }
        for (i = 0; i < cases; i++ ) {
            buff = n[i] / 2;
            if (n[i] == 1) {
                sum = -1;
            }


            if (!(n[i] & 1)) {
                for (j = 2; j < buff; j++) {
                    if (n[i] % j == 0) {
                        sum += n[i] / j + j;
                        buff /= j;
                    }
                }
            }


            else {
                for (j = 3; j < buff; j += 2) {
                    if (n[i] % j == 0) {
                        if (n[i] / j == j) { sum += j; break; }
                        else sum += n[i] / j + j;
                    }
                    buff /= j;
                }
             }
            printf("%d\n", ++sum);
            sum = 0;
        }
        return 0;
    }
    /* @END_OF_SOURCE_CODE */

但它还不够快.有什么建议？

Answer 1

我已经更新了下面的代码,以便尽快终止.在MacBookPro6,1(2.66 GHz Intel Core i7)上运行1到500,000的所有整数,用Apple GCC 4.2.1和-O3编译.

它使用σ的公式_X(Ñ在的属性部分)Wikipedia页面为除数函数.使用预先计算的素数列表可以更快地完成.(需要126个才能支持高达500,000的输入,这会将时间减少到不到四分之一秒.)还有一些可以消除的分歧,代价是稍微混乱代码.

//  Return the least power of a that does not divide x.
static unsigned int LeastPower(unsigned int a, unsigned int x)
{
    unsigned int b = a;
    while (x % b == 0)
        b *= a;
    return b;
}


//  Return the sum of the proper divisors of x.
static unsigned int SumDivisors(unsigned int x)
{
    unsigned int t = x;
    unsigned int result = 1;

    //  Handle two specially.
    {
        unsigned int p = LeastPower(2, t);
        result *= p-1;
        t /= p/2;
    }

    //  Handle odd factors.
    for (unsigned int i = 3; i*i <= t; i += 2)
    {
        unsigned int p = LeastPower(i, t);
        result *= (p-1) / (i-1);
        t /= p/i;
    }

    //  At this point, t must be one or prime.
    if (1 < t)
        result *= 1+t;

    return result - x;
}