LNH_Sniper 发表于 2011-7-5 09:52:47

算法每日一题（二）

问题：如果一个数恰好等于它的因子之和，那么这个数就被称为完全数。例如6的因子为1，2，3，而6 = 1 + 2 + 3，因此6是一个完全数。请编写一个程序，求出1000以内的完全数。

winddyj 发表于 2011-7-5 10:19:19

貌似是 C语言经典例题100 里面的题目

winddyj 发表于 2011-7-5 10:21:40

翻了下,果然写过
#include <stdio.h>

int main(void)
{
    int i,j,m;
    for(i=4;i<1000;i++)
      for(j=1,m=0;j<i;j++)
      {
            if(i%j==0)
            {
                m+=j;
                //printf("%d+",j);
            }
            if(j==i-1)
            {
                if(m==i)
                  printf("%d\n",i);
            }
      }
}

仰望天上的光 发表于 2011-7-5 12:59:14

#include<stdio.h>
#include<math.h>

//判素数
int ispri(int n);
int main(void){
        int i;
        for(i=2;i<=7;++i){
                int m = pow(2,i)-1;
                //用欧几里德完全数定理
                if(ispri(i)&&ispri(m)){
                        int k = pow(2,i-1);
                        printf("%d\n",k*m);
                }
        }
}

int ispri(int n){
        int i,m=sqrt(n)+1;
        for(i=2;i<=m && i<n;++i)
                if(n%i==0) return 0;
        return 1;
}

chao_prince 发表于 2011-7-5 14:21:22

继续努力。。/*
**        问题：如果一个数恰好等于它的因子之和，
**        那么这个数就被称为完全数。
**        例如6的因子为1，2，3，
**        而6 = 1 + 2 + 3，因此6是一个完全数。
**        请编写一个程序，求出1000以内的完全数。
**        By 小锅
**        7/5/11
*/

#include <stdio.h>

int main()
{
        int i, j, sum;

        for( i = 2; i < 1000; i++ )
        {
                sum = 0;
                for( j = 1; j < i; j++ )
                {
                        if( i % j == 0 )
                        {
                                sum += j;
                        }
                        if( j == i-1 )
                        {
                                if( sum == i )
                                        printf( "%-5d\n", sum );
                        }
                }
        }
        return 0;
}

LNH_Sniper 发表于 2011-7-5 17:51:50

仰望天上的光 发表于 2011-7-5 12:59 static/image/common/back.gif


数据测试有些问题，
6、28、496、8128，最后一个数据不是规定数据。

LNH_Sniper 发表于 2011-7-5 18:04:14

#include "stdio.h"

int factorSum( int a ) //i是a的一个因子
{
int i, sum = 0;
for( i = 1; i < a; i++ )
{
if( a % i == 0 )
sum = sum + i;
}

return sum;
}

int perfextnumber( int a ) //判断a是否是完全数
{
if( a == factorSum(a) )
return 1;
else
return 0;
}

int main()
{
int a;
printf("There are following perfect numbers 1~10000 are:\n");
for( a = 1; a <= 1000; a++ )
{
if( perfextnumber(a) )
printf("%d ", a);
}

return 0;
}

仰望天上的光 发表于 2011-7-5 19:11:17

LNH_Sniper 发表于 2011-7-5 17:51 static/image/common/back.gif
数据测试有些问题，
6、28、496、8128，最后一个数据不是规定数据。

多求出一个超过1000范围的完全数而已。算法主要应该注重效率。用该算法效率极高，是其它算法的将近100倍。

仰望天上的光 发表于 2011-7-5 19:27:07

LNH_Sniper 发表于 2011-7-5 17:51 static/image/common/back.gif
数据测试有些问题，
6、28、496、8128，最后一个数据不是规定数据。

其实只要把
for(i=2;i<=7;++i)
改为
for(i=2;i<7;++i)
就可以得到LZ的答案，但仅仅在1000内找实在提现不出算法的力量，我觉得应该把这道题改为：求出1到18位的所有完全数，才能真正体现算法的力量。（一般的算法就等着死机吧）

LNH_Sniper 发表于 2011-7-5 22:07:10

仰望天上的光 发表于 2011-7-5 19:27 static/image/common/back.gif
其实只要把
for(i=2;i

没错，算法注重效率，但，同时对不同问题，采取最佳的解决方式，方为上品。

因此，此题，范围很小，我选择了穷举法。

与君共勉吧。

asd82937121 发表于 2011-7-6 11:05:25

如果不算这个数本身的话最大的因子不过是这个数的二分之一， 循环到二分之一即可

猪猪BBUn咕咕 发表于 2013-11-18 15:33:45

谢谢啦~有空的话我会看一下
页: [1]
查看完整版本: 算法每日一题（二）