LNH_Sniper 发表于 2011-7-6 09:08:49

算法每日一题（三）

问题：如果整数A的全部因子（包括1，不包括A本身）之和等于B，并且整数B的全部因子（包括1，不包括B本身）之和等于A，则称整数A和B为亲密数。求解3000以内的全部亲密数。

asd82937121 发表于 2011-7-6 10:56:28

你也不说这A 和B 允不允许相等啊
以下是最直观的求简便算法


#include "stdio.h"
#include "math.h"
void main()
{
        int A,i,sumB,sumA;
        for(A=2;A<=3000;A++)
        {
                sumA=0;sumB=0;
                for(i=1;i<=A/2;i++)
                {
                        if(!(A%i)) sumB+=i;
                }
                for(i=1;i<=sumB/2;i++)
                {
                        if(!(sumB%i))sumA+=i;
                }
                if((sumA==A)&&(A<=sumB))
                {
                        printf("%d,%d\n",A,sumB);
                }
       
        }

}

仰望天上的光 发表于 2011-7-6 11:18:34

纯穷举...#include<stdio.h>
#include<math.h>
int get_facts_sum(int n);
int main(){
        int n;
        for(n=210;n<=3000;++n){
                int s = get_facts_sum(n);
                if(s<=n)        continue;
                if(n==get_facts_sum(s)){
                        printf("%d\t%d\n",n,s);
                }
        }
}
int get_facts_sum(int n){
        int s=1,i;
        for(i=2;i<=sqrt(n);++i){
                if(n%i==0)        s+=i+n/i;
        }
        return s;
}

asd82937121 发表于 2011-7-6 11:27:40

光光 ，他这个是求因子 不是质因子你用sqrt 是不行的

仰望天上的光 发表于 2011-7-6 12:41:35

asd82937121 发表于 2011-7-6 11:27 static/image/common/back.gif
光光 ，他这个是求因子 不是质因子你用sqrt 是不行的

为什么不行？每次得到一对因子，这一对因子里必定有一个<=sqrt(n)

仰望天上的光 发表于 2011-7-6 12:43:10

asd82937121 发表于 2011-7-6 10:56 static/image/common/back.gif
你也不说这A 和B 允不允许相等啊
以下是最直观的求简便算法



不允许相等的，相等就变成“完全数”了。

asd82937121 发表于 2011-7-6 13:13:30

程序没看明白   不过运行起来确实比我的快一点

LNH_Sniper 发表于 2011-7-6 20:47:33

题目分析：由于亲密数是两个数之间的关系。也就说，不能立刻判断一个整数A是否有亲密数，更不知道它的亲密数是多少。因此，在算法的选择上，我采用了一种具有选择性质的算法来查找一定范围内的亲密数，此算法效率不高，但直观有效。

在一个数集{ a1, a2, a3,..........., an }中寻找亲密数，可以针对某一个元素，在其他的元素中寻找该元素的亲密数。这样即划分两个集合：A、B；最初数集中所有的元素都放在集合B中，然后从B中任意选择一个元素放入集合A中，同时在集合B中删去该元素。然后在集合B中的其他元素中寻找刚刚放入集合A中的那个元素的亲密数。

重复上述过程，直到B集合为空。



#include "stdio.h"

int factorSum( int elem_a ) //求a的因子和
{
int i, sum = 0;
for( i = 1; i < elem_a; i++ )
{
if( elem_a % i == 0 )
sum = sum + i;
}

return sum;
}

int isfriend( int elem_a_factor, int elem_b_factor, int elem_a, int elem_b ) //判断A、B两个数是否是完全数其中elem_a、elem_b分别是A、B;elem_a_factor、elem_b_factor 分别是A的因数和、B的因数和

{
if( elem_a_factor == elem_b && elem_b_factor == elem_a )
return 1;
else
return 0;
}

void friendly( void )
{
int elem_a, elem_b, temp;
for( elem_a = 1; elem_a <= 3000; elem_a++ )
temp = factorSum(elem_a);
for( elem_a = 1; elem_a <= 3000; elem_a++ )
{
if( temp != -1 )
{
for( elem_b = elem_a + 1; elem_b <= 3000; elem_b++ )
{
if( isfriend( temp, temp, elem_a, elem_b ) )
{
printf("(%d,%d) ",elem_a,elem_b);
temp = -1;
}
}
}
}
}

int main()
{
printf("There are following friendly numbers from 1 to 30000\n");
friendly();
printf("\n");
return 0;
}

dps521 发表于 2015-11-28 11:16:24

:smile:smile:smile:smile:smile:smile
页: [1]
查看完整版本: 算法每日一题（三）