"有趣的整数"类习题、面试题详解（第二篇）

第一篇链接：“有趣的整数”类习题、面试题详解（第一篇）

6题：回文数

回文数是指一个多位数在按位读时，无论是从左向右还是从右向左读取，其结果都是一样的。例如：11、22、101等。编写程序求出1000以内的回文素数和平方回文数。

（1）回文素数：既是回文数同时又是素数。例如：121，151等。

（2）平方回文数：是另一个整数的平方。例如：121，484等。

#include 

int IsPrime(int m)
{
    int i, result = 1;
    for (i = 2; i * i 

解析：回文素数：依次比较最高位和最低位，次高位和次低位…，然后再判断是否为素数。平方回文数：依次比较最高位和最低位，次高位和次低位…，然后再判断是否为平方数。实现上，可将每位分离保存到数组中，然后对应比较。




7题：哥德巴赫猜想
每个不小于6的偶数都是两个素数之和。编写程序验证哥德巴赫猜想。（为了简化程序，本例只是以计算机能表示的整数范围之内的数进行处理，如果要处理更多位的整数，则需要编写代码对大整数运算进行处理）
#include 
int main(void)
{
    int n, m, i, flag;
    scanf("%d", &n);

    for (m = 6; m 
解析：改进算法：将指定范围内素数筛选出来，就不需要每次都判断某个数是否为素数。



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   
#include   
#include   
  
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  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 = 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 
#include 
#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  maxp)
						maxp = j;
				}
			}
		}

		for (i = 0; i <= maxp; i++)
			printf("%d ", p[i]);
		printf("\n");
	}

	return 0;
}