"有趣的整数"类习题、面试题详解（第一篇）
来源：程序员人生 发布时间：2014-11-03 08:06:49 阅读次数：2771次
1题：完数
如果1个数恰好等于其因子之和，这个数就称为完数。例如：6 = 1 + 2 + 3。编写程序，求出10000之内的所有完数。
#include <stdio.h>
#define MAXN 50000
int main(void)
{
int divisor[MAXN]; //Use to save factors
int p = 0, count = 0, num = 0;
int numsave = 0, divisortest = 0, i = 0;
for (num = 1; num < 10000; num++)
{
p = 0;
numsave = num;
for (divisortest = 1; divisortest < num / 2 + 1; divisortest++)
{
if (num % divisortest == 0)
{
divisor[p++] = divisortest;
numsave -= divisortest;
}
}
if (numsave == 0)
{
printf("%d:%4d = ", ++count, num);
for (i = 0; i < p - 1; i++)
{
printf("%d + ", divisor[i]);
}
printf("%d
", divisor[p - 1]);
}
}
return 0;
}
解析：虽然从结果来看MAXN只需取15便可，但如果你这么做必定会致使段毛病。由于num = 9720时，它需要47个数组单元来存储其因子，访问的数组过界了。
2题：水仙花数
数值等于各位数字的3次幂之和，例如：153 = 1^3 + 5^3 + 3^3，称为水仙花数。编程求出所有水仙花数。
#include <stdio.h>
int main(void)
{
int i, j, k, num;
for (num = 100; num < 1000; num++)
{
i = num / 100;
k = num % 10;
j = num % 100 / 10;
if (i * i * i + j * j * j + k * k * k == num)
printf("%d
", num);
}
return 0;
}
3题：密切数
假定有a、b两个数，若a的所有因子之和等于b，b的所有因子之和等于a（因子包括1不包括本身），并且a不等于b，则称a和b是1对密切数。例如：整数220的因子之和为284，284的因子之和为220，所以220和284是1对密切数。要求出5000之内的密切数。
#include <stdio.h>
#define MAXN 5000
int main(void)
{
int i, a, b, tempa, tempb;
int fact_a[MAXN] = {0}, pa;
int fact_b[MAXN] = {0}, pb;
for (a = 1; a < 5000; a++) //a is bigger
{
tempa = 0;
tempb = 0;
pa = 0;
pb = 0;
for (i = 1; i < (a / 2 + 1); i++)
{
if (a % i == 0)
{
fact_a[pa++] = i;
tempa += i;
}
}
if (tempa > a) //to ensure b > a
{
for (i = 1; i < (tempa / 2 + 1); i++)
{
if (tempa % i == 0)
{
fact_b[pb++] = i;
tempb += i;
}
}
}
if (tempb == a)
{
printf("%d AND %d:
", a, tempa);
printf("%d = ", a);
for (i = 0; i < pa - 1; i++)
printf("%d + ", fact_a[i]);
printf("%d
", fact_a[i]);
printf("%d = ", tempa);
for (i = 0; i < pb - 1; i++)
printf("%d + ", fact_b[i]);
printf("%d
", fact_b[i]);
}
}
return 0;
}
解析：220与284是1对密切数，改变顺序后284与220就不能再算做密切数了。
4题：自守数
自守数是指1个数的平方结果的后几位数等于该数本身的这样1种自然数。例如：6的平方等于36，尾数是6，所以6是自守数。25的平方等于625，尾数是25，所以25是自守数。编程求出指定范围内的自守数。分析以下：
（1）比较自然的思路是：计算数n的平方，再截取相应位数与n比较，若相等则表示找到自守数。由于计算机变量存储范围有限，这类思路对过大的整数没办法计算。
（2）为了计算更大的自守数，需采取以下思路。例如：625 * 625，实际只关心积的后3位。
1）对个位数与被乘数相乘的积中，用被乘数625与乘数的个位5相乘；
2）对10位与被乘数相乘的积中，用被乘数的后两位25与乘数的10位20相乘；
3）对百位数与被乘数相乘的积中，用被乘数的后1位5与乘数的百位600相乘。
将以上各位相乘的积累加，再取后3位便可。
#include <stdio.h>
int main(void)
{
int a, b, t_a;
long n, m, tempm, sum, x , y;
scanf("%ld", &n);
for (m = 1; m < n; m++)
{
tempm = m;
a = 1;
b = 10;
sum = 0;
while (tempm > 0)
{
tempm /= 10;
a *= 10;
}
t_a = a;
while (t_a > 10)
{
x = m % t_a;
y = m % b - m % (b / 10);
sum = (sum + (x * y)) % a;
t_a /= 10;
b *= 10;
}
if (sum == m)
printf("%ld ", m);
}
printf("
");
return 0;
}
5题：素数
除1和本身以外，没有别的因数的数。两种思路：（1）普通法；（2）Eratosthenes挑选法。
//普通法
int IsPrime(int m)
{
int i, flag = 1;
for (i = 2; i * i < m + 1; i++)
{
if (m % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
//挑选法
#include <stdio.h>
#define MAXN 1000
int main(void)
{
int Prime[MAXN + 1], i, j;
for (i = 2; i < MAXN + 1; i++)
Prime[i] = 1;
for (i = 2; i * i < MAXN + 1; i++)
{
if (Prime[i] == 1)
{
for (j = 2 * i; j < MAXN + 1; j++)
{
if (j % i == 0)
Prime[j] = 0;
}
}
}
for (i = 2; i < MAXN + 1; i++)
{
if (Prime[i])
printf("%d ", i);
}
printf("
");
return 0;
}
解析：普通法适用于判断某数是不是为素数，挑选法适用于求指定范围内的素数。
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
