"有趣的整數"類習題、面試題詳解（第一篇）
來源：程序員人生 發布時間：2014-11-03 08:06:49 閱讀次數：2909次
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;
}
解析：普通法適用于判斷某數是不是為素數，挑選法適用于求指定范圍內的素數。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
