求4位数以内的相亲数对
     2500年前数学大师毕达哥拉斯发现，220与284两数之间存在下列奇妙的联系：
220的真因数之和为1+2+4+5+10+11+20+22+44+55+110=284
284的真因数之和为1+2+4+71+142=220
毕达哥拉斯把这样的数对a,b称为相亲数：a的真因数（小于本身的因数）之和为b，而b的真因数之和为a。

要用WINT C演绎出来 每次都编译失败

程序呢？

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

int sum(int n) {
    int i, s = 0;

    for(i = 1; i <= (n / 2); i++) {
        if(0 == n % i) {
            s += i;
        }
    }

    return s;
}

int *pnum(int n) {
    int i, j, *pn = NULL, *p = NULL;
    pn = malloc(2 * n * sizeof(int));
    p = pn;

    if(p == NULL) {
        printf("malloc error!\n");
        exit(1);
    }

    for(i = 1, j = 1; i < 2 * n; j++, i += 2) {
        *p = j;
        p++;
        *p = sum(j);
        p++;
    }

    return pn;
}

int main(void) {
    int N, i, j, *p = NULL;
    printf("请输入一个正整数N，以查找相亲数对，数对中的每个数值均不大于N：");
    scanf("%d", &N);
    p = pnum(N);

    for(i = 0 ; i < 2 * N; i += 2) {
        for(j = 2; j < 2 * N; j += 2) {
            if(*(p + i) == *(p + j + 1)
                    && (*(p + i + 1) == *(p + j))
                    && (*(p + i) < * (p + i + 1))) {
                printf("%d\t%d\n", *(p + i), *(p + i + 1));
            }
        }
    }

    free(p);
    return 0 ;
}

想不出优化的算法
上面的代码在查找很大数值内的相亲数对时
会比较慢.....

请高手给出好的算法

#include <stdio.h>
#include <stdlib.h>
int sum(int n) {
    int i, s = 0;

    for(i = 1; i <= (n / 2); i++) {
        if(0 == n % i) {
            s += i;
        }
    }
    return s;
}

int sum(int n);
int main(void)
 {
    int  i, j,ri,rei;
    for(i = 2 ; i < 9999; i++)
        { ri=sum(i);
          rei=sum(ri);
          if(i==rei&& i!=ri) printf("{%d,%d是相亲数}\n",i,ri);
        }  
    return 0 ;
}

7楼的代码不错
没用数组指针
也没用循环嵌套
变量值比较完就扔
内存占用应该也较小
就是sum()函数调用的次数翻倍了

没有把重复项去掉，加一句 i=ri;

[ 本帖最后由 comewest 于 2014-12-10 11:00 编辑 ]

换了个算法，请直接跳到21楼 https://bbs.bccn.net/viewthread.php?tid=439762&page=3#pid2457661

这题难点主要在于怎样快速求真因数之和，但很遗憾，没想出什么好办法出来。
于是，简单地将你的代码整理了一下。在十万以内，只快了两百多倍。

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

int main( void )
{
    //unsigned n;
    //printf( "%s", "请输入一个正整数N，以查找相亲数对，数对中的每个数值均不大于N：" );
    //if( scanf("%u",&n) != 1 )
    //    return 1;
    unsigned n = 100000;

    unsigned* p = malloc( sizeof(unsigned)*n );
    if( !p )
        return 2;

    for( size_t i=0; i!=n; ++i )
    {
        p[i] = 1;
        for( unsigned j=2; j*j<=(i+1); ++j )
            if( (i+1)%j == 0 )
                p[i] += j + (j*j==i+1?0:(i+1)/j);
    }

    for( size_t i=0; i!=n; ++i )
        if( p[i]>i+1 && p[i]<=n && p[p[i]-1]==i+1 )
            printf( "%u\t%u\n", i+1, p[i] );

    free( p );
    return 0;
}

耗时 0.078 秒
输出
220     284
1184    1210
2620    2924
5020    5564
6232    6368
10744   10856
12285   14595
17296   18416
63020   76084
66928   66992
67095   71145
69615   87633
79750   88730


[ 本帖最后由 rjsp 于 2014-12-12 10:22 编辑 ]