编程练习——完全数计算

完全数计算

• 时间限制：1秒
• 空间限制：32768K

描述

• 完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
• 它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
• 例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
• 给定函数 count(int n)，用于计算 n 以内 (含n) 完全数的个数。计算范围：0 < n <= 500000
• 返回 n 以内完全数的个数。 异常情况返回 -1

/**
 * 
 *  完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
 *  它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
 *  例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
 * 
 *  给定函数count(int n),用于计算n以内(含n)完全数的个数
 * @param n  计算范围, 0 < n <= 500000
 * @return n 以内完全数的个数, 异常情况返回-1
 * 
 */    

public   static   int  count( int  n)

• 输入描述：输入一个数字
• 输出描述：输出完全数的个数
• 示例：输入 1000，输出 3

C 代码实现

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

/* 判断一个数是否为完全数 */
static int is_perfect_number(unsigned int num)
{
	int i, sum=1;

	/* 利用真因子关于根号对称出现的特点，范围缩小到sqrt(num) */
	for(i=2; i<=sqrt(num); i++) {
		if(num % i == 0) {
			sum += i;
			sum += num/i;
		}
	}

	if(sum == num && num != 1)
		return num;
	else
		return 0;
}

/* 计算n以内的完全数的个数 */
static int count(int n)
{
	int i, cnt=0;

	if(n <= 0 || n > 500000)
		return -1;

	for(i=1; i<=n; i++) {
		if(is_perfect_number(i)) {
			printf("%d\n", i);
			cnt++;
		}
	}
	return cnt;
}

int main(void)
{
	int n=0, cnt=0;

	printf(">> ");
	scanf("%d", &n);

	if(-1 == (cnt = count(n))) 
		printf("异常\n");
	else
		printf("Total perfect number between 1 and %d: %d\n", n, cnt);

	return 0;
}

代码编译执行如下：