Question

C语言上机题目求解：在6至5000内找出所有的亲密数对，

若a.b为一对亲密数，a的因子和等于b，b的因子和等于a,且a不等于b

Answer 1

贴一个比楼上还要快的算法。嘿嘿~~！
不过C语言平常上机用不上太快的算法。
。。。。。。。。。。。。。。。。。。。。。。。

#include<stdio.h>
#define N 5001
int main()
{
int i,j;
int sum[N]; //用来储存i的因子和的数组。
int a,b;
int hh[N]; //用来做标记的数组。
for(i=1;i<N;i++)
sum[i]=hh[i]=1; //1是所有数的因子 所以sum初始为1。

for(i=2;i<N;i++)
for(j=i+i;j<N;j+=i) //找到所有i的倍数j
sum[j]+=i; //j的因子和 +i

for(i=6;i<N;i++)
{
a=sum[i]; //a为i的因子和。
if(a<N && sum[a]==i && hh[i] && a!=i)
{
printf("%d,%d\n",i,a);
hh[i]=hh[a]=0; //把i和a标记掉，防止输出两次。
}
}
return 0;
}
。。。。。。。。。。。。。。。。。。。。。。。。。
这样 一对亲密数 就输出了两次。。

#include<stdio.h>
#define N 5001
int main()
{
int i,j;
int sum[N]; //用来储存i的因子和的数组。
int a,b;
int hh[N]; //用来做标记的数组。
for(i=1;i<N;i++)
sum[i]=1; //1是所有数的因子 所以sum初始为1。

for(i=2;i<N;i++)
for(j=i+i;j<N;j+=i) //找到所有i的倍数j
sum[j]+=i; //j的因子和 +i

for(i=6;i<N;i++)
{
a=sum[i]; //a为i的因子和。
if(a<N && sum[a]==i && a!=i)
{
printf("%d,%d\n",i,a);
}
}
return 0;
}

Answer 2

//电脑速度慢的话，请将5000改为1000。
#include<stdio.h>
void main()
{
int getsum(int n);
int x,y;
for(x=6;x<5000;x++)//电脑速度慢的话，请将5000改为1000。
for(y=6;y<5000;y++)//电脑速度慢的话，请将5000改为1000。

if((x==getsum(y))&&(y==getsum(x))&&x!=y)
printf("%-5d%-5d%\n",x,y);
}
int getsum(int n)

{
int i,a=1;
for(i=2;i<=n/2;i++)
if(!(n%i))
a=a+i;
return a;
}

Answer 3

#include<stdio.h>
int x_sum(int x)
{//求因子和
int r = 1;
for (int i=2; i<=x/2; i++)
if (x % i == 0)
r = r + i;
return r;
}

int main()
{
int a = 0;
int b = 0;
for (int i=6; i<=5000; i++)
{
a = x_sum(i);
for (int j=i+1; j<=5000; j++)
{
b = x_sum(j);
if (a == j && b == i)
{//亲密数判断条件
printf("%d 是 %d 的亲密数\r\n", i, j);
}
}
}
return 0;
}

Answer 4

LS算法不好，速度太慢
#include<stdio.h>
#define Max 5000
void main()
{
int a=5,i,j,s,m;
do{
a++;
s=1;
for(i=2;i<=a/2;i++)if(a%i==0)s=s+i;
if(s<=a||s>Max)continue;
m=1;
for(j=2;j<=s/2;j++) if(s%j==0)m=m+j;
if(m==a)printf("%d,%d\n",a,s);
}while(a<=Max);
}

Answer 5

surface不在身边，敲不了。。。说下思路吧，嵌套for循环，定义一个函数求因子和，然后用if判断