第一篇链接：“有趣的整数”类习题、面试题详解（第一篇）
6题：回文数
回文数是指一个多位数在按位读时，无论是从左向右还是从右向左读取，其结果都是一样的。例如：11、22、101等。编写程序求出1000以内的回文素数和平方回文数。
（1）回文素数：既是回文数同时又是素数。例如：121，151等。
（2）平方回文数：是另一个整数的平方。例如：121，484等。
#include <stdio.h>
int IsPrime(int m)
{
int i, result = 1;
for (i = 2; i * i < m + 1; i++)
{
if (m % i == 0)
{
result = 0;
break;
}
}
return result;
}
int IsSquare(int m)
{
int i, result = 0;
for (i = 2; i * i <= m; i++);
if (m == (i - 1) * (i - 1))
result = 1;
return result;
}
//回文素数
void HuiWPrime()
{
int i, j, k;
int result;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
if (i == 0 && j == 0)
continue;
for (k = 1; k < 9; k++)
{
if ((i == 0 && j != k) || (i != 0 && i != k))
continue;
result = i * 100 + j * 10 + k;
if (IsPrime(result))
printf("%d ", result);
}
}
}
printf("\n");
return;
}
//平方回文数
void HuiWSquare()
{
int i, j, k;
int result;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
if (i == 0 && j == 0)
continue;
for (k = 1; k < 9; k++)
{
if ((i == 0 && j != k) || (i != 0 && i != k))
continue;
result = i * 100 + j * 10 + k;
if (IsSquare(result))
printf("%d ", result);
}
}
}
printf("\n");
return;
}
解析：回文素数：依次比较最高位和最低位，次高位和次低位…，然后再判断是否为素数。平方回文数：依次比较最高位和最低位，次高位和次低位…，然后再判断是否为平方数。实现上，可将每位分离保存到数组中，然后对应比较。
7题：哥德巴赫猜想
每个不小于6的偶数都是两个素数之和。编写程序验证哥德巴赫猜想。（为了简化程序，本例只是以计算机能表示的整数范围之内的数进行处理，如果要处理更多位的整数，则需要编写代码对大整数运算进行处理）
#include <stdio.h>
int main(void)
{
int n, m, i, flag;
scanf("%d", &n);
for (m = 6; m < n; m += 2)
{
flag = 1;
for (i = 2; i < m / 2 + 1; i++)
{
if (IsPrime(i) && IsPrime(m - i))
{
printf("%d = %d + %d\n", m, i, m - i);
flag = 0;
break;
}
}
if (1 == flag)
printf("找到不符合要求的偶数:%d\n", m);
}
return 0;
}
解析：改进算法：将指定范围内素数筛选出来，就不需要每次都判断某个数是否为素数。
8题：最大公约数和最小公倍数
思路1：欧几里得算法
欧几里得算法是采用辗转相除的方法来求最大公约数。
int Gcd(int m, int n)
{
int a, b, r;
a = m >= n ? m : n;
b = m + n - a;
if (b == 0)
return a;
while ((r = (a % b)) != 0)
{
a = b;
b = r;
}
return b;
}
int Lcm(int m, int n)
{
return (m * n) / Gcd(m, n);
}
思路2：Stein算法
欧几里得算法简单，效率也很好，该算法的缺陷只有在大素数时才会显现出来，这主要是由计算机能表示的整数范围决定的。一般整数最多使用64位来表示，要计算这样两个整数之间的模很简单，但对于更大的素数，就需要由用户来设计计算两数的模的程序。对于现代密码算法，要求计算128位以上的素数的情况相当普遍，为了提高效率，最好不使用除法和取模运算。
#define ABS(x) (x) > 0 ? (x) : -(x)
#define MIN(x, y) (x) < (y) ? (x) : (y)
int Gcd(int m, int n)
{
int result, temp;
if (m == 0)
return n;
if (n == 0)
return m;
if (((m & 0x1) == 0) && ((n & 0x1) == 0)) //m和n都是偶数
{
m >>= 1;
n >>= 1;
result = Gcd(m, n) << 1;
}
else if ((m & 0x1) == 0) //m是偶数，n是奇数
{
m >>= 1;
result = Gcd(m, n);
}
else if ((n & 0x1) == 0) //n是偶数，m是奇数
{
n >>= 1;
result = Gcd(m, n);
}
else if ((m & 0x1) && (n & 0x1)) //m和n都是奇数
{
temp = ABS(m - n);
n = MIN(m, n);
result = Gcd(temp, n);
}
return result;
}
9题：阶乘
思路1：递归与迭代
//递归
long factorial(int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
}
#endif
//迭代
long factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
思路2：大整数阶乘
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
void carry(int bit[], int n) //处理进位
{
int carry = 0, i;
for (i = 0; i <= n; i++)
{
bit[i] += carry;
if (bit[i] <= 9)
{
carry = 0;
}
else if (bit[i] > 9 && i < n) //不是最高位
{
carry = bit[i] / 10;
bit[i] = bit[i] % 10;
}
else if (bit[i] > 9 && i >= n) //是最高位
{
while (bit[i] > 9)
{
carry = bit[i] / 10;
bit[i] = bit[i] % 10;
bit[++i] = carry;
}
}
}
return;
}
int main(void)
{
int m, n, i, j, pos;
int *fact;
double temp = 0;
printf("请输入大整数m:");
scanf("%d", &m);
for (i = 1; i <= m; i++)
{
temp += log10(i);
}
n = (int)temp + 1; //求出m!的位数
if (!(fact = (int *)malloc(sizeof(int) * n)))
{
return 0;
}
for (i = 0; i < n; i++)
{
*(fact + i) = 0;
}
fact[0] = 1; //开始时个位数字为1
for (i = 2; i <= m; i++)
{
for (j = n - 1; j >= 0; j--)
{
if (fact[j] != 0) //查找最高位
{
pos = j;
break;
}
}
for (j = 0; j <= pos; j++)
{
fact[j] *= i;
}
carry(fact, pos);
}
for (i = n - 1; i >= 0; i--)
{
if (fact[i] != 0)
{
pos = i;
break;
}
}
m = 0;
printf("大整数m的阶乘为:\n");
for (i = pos; i >= 0; i--)
{
printf("%d", fact[i]);
m++;
if (m % 5 == 0)
{
printf(" ");
}
if (40 == m)
{
printf("\n");
m = 0;
}
}
printf("\n");
printf("大整数m的阶乘的总位数是:%d\n", n);
free(fact);
fact = NULL;
return 0;
}
解析：使用数组保存阶乘每一位结果。即使使用long型保存每一位相乘的结果，能求阶乘的最大数仍然有限制。若要求出不限制数的阶乘，数据存储和处理还需要更复杂的算法。
10题：因子和阶乘
输入正整数n（2 <= n<= 100），把阶乘n! = 1 * 2 * 3*…*n分解成素因子相乘的形式，从小到大输出各个素数（2、3、5、…）的指数。例如：825 = 3 * 5^2 * 11应表示成（0,1,2,0,1），表示分别有0、1、2、0、1个2、3、5、7、11。你的程序应忽略比最大素因子更大的素数（否则末尾会有无穷多个0）。
样例输入：
5
53
样例输出：
5! = 3 1 1
53! = 4923 12 8 4 4 3 2 2 1 1 1 1 1 1 1
#include <stdio.h>
#include <string.h>
#define MAXN 100
int PrimeTable[MAXN], count = 0;
int IsPrime(int m)
{
for (int i = 2; i * i <= m; i++)
if (m % i == 0)
return 0;
return 1;
}
int main(void)
{
int i, j, m, p[MAXN], maxp, tmp; //p为指数
for (i = 2; i <= MAXN; i++) //构造素数表
{
if (IsPrime(i))
PrimeTable[count++] = i;
}
while (scanf("%d", &m) == 1)
{
memset(p, 0, sizeof(p));
maxp = 0;
printf("%d! = ", m);
for (i = 1; i <= m; i++)
{
tmp = i;
for (j = 0; j < count; j++)
{
while (tmp % PrimeTable[j] == 0)
{
tmp /= PrimeTable[j];
p[j]++;
if (j > maxp)
maxp = j;
}
}
}
for (i = 0; i <= maxp; i++)
printf("%d ", p[i]);
printf("\n");
}
return 0;
}