算法每日一题（三）

LNH_Sniper

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

asd82937121

你也不说这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);
                }
       
        }

}

仰望天上的光

纯穷举...

1. #include<stdio.h>
   
2. #include<math.h>
   
3. int get_facts_sum(int n);
   
4. int main(){
   
5.         int n;
   
6.         for(n=210;n<=3000;++n){
   
7.                 int s = get_facts_sum(n);
   
8.                 if(s<=n)        continue;
   
9.                 if(n==get_facts_sum(s)){
   
10.                         printf("%d\t%d\n",n,s);
    
11.                 }
    
12.         }
    
13. }
    
14. int get_facts_sum(int n){
    
15.         int s=1,i;
    
16.         for(i=2;i<=sqrt(n);++i){
    
17.                 if(n%i==0)        s+=i+n/i;
    
18.         }
    
19.         return s;
    
20. }

复制代码

asd82937121

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

仰望天上的光

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

                               
登录/注册后可看大图

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

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

仰望天上的光

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

                               
登录/注册后可看大图

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

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

asd82937121

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

LNH_Sniper

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

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

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

1. #include "stdio.h"
   
2. 
   
3. int factorSum( int elem_a ) //求a的因子和
   
4. {
   
5. int i, sum = 0;
   
6. for( i = 1; i < elem_a; i++ )
   
7. {
   
8. if( elem_a % i == 0 )
   
9. sum = sum + i;
   
10. }
    
11. 
    
12. return sum;
    
13. }
    
14. 
    
15. 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的因数和
    
16. 
    
17. {
    
18. if( elem_a_factor == elem_b && elem_b_factor == elem_a )
    
19. return 1;
    
20. else
    
21. return 0;
    
22. }
    
23. 
    
24. void friendly( void )
    
25. {
    
26. int elem_a, elem_b, temp[3001];
    
27. for( elem_a = 1; elem_a <= 3000; elem_a++ )
    
28. temp[elem_a] = factorSum(elem_a);
    
29. for( elem_a = 1; elem_a <= 3000; elem_a++ )
    
30. {
    
31. if( temp[elem_a] != -1 )
    
32. {
    
33. for( elem_b = elem_a + 1; elem_b <= 3000; elem_b++ )
    
34. {
    
35. if( isfriend( temp[elem_a], temp[elem_b], elem_a, elem_b ) )
    
36. {
    
37. printf("(%d,%d) ",elem_a,elem_b);
    
38. temp[elem_b] = -1;
    
39. }
    
40. }
    
41. }
    
42. }
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47. printf("There are following friendly numbers from 1 to 30000\n");
    
48. friendly();
    
49. printf("\n");
    
50. return 0;
    
51. }

复制代码

dps521

:smile:smile:smile:smile:smile:smile