数论（各种数）

一

本文收集了一些常用的基础的数的简单讲解，包括：最大公约数与最小公倍数、素数、水仙花数、完数与回文数。

最大公约数与最小公倍数之前已经出过，点击链接即可访问。

二、素数

（1）什么叫素数？

素数又称质数（prime number），有无限个。

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

注意：定义中素数的范围为大于1的自然数，因此1不是素数。

（2）关于求法？

根据素数的概念（除了1和它本身以外不再有其他因数），使用穷举的方法即可解决。

（3）代码示例

以下代码可以参考：

int isPrime(int a)
{
	for (int i = 2; i < (int)(sqrt(a)); i++)
	{
		if (a % i == 0)
		{
			return 0;
		}
	}
	return 1;
}
           

注意：

1. 一个数的约数的范围为 1 < a < 根号n，利用这点，便可以压缩寻找的范围；
2. 此函数的作用是判断一个数是否为素数，若是则返回 1 ，否则返回 0 .

利用以上代码便可以打印1 ~ 1000内的素数：

#include <iostream>
#include <iomanip>
using namespace std;
int isPrime(int);

int main()
{
	cout << right;      //右对齐
	int count = 0;     //用于计数
	
	for (int i = 2; i < 1000; i++)
	{
		if (isPrime(i))
		{
			count++;
			cout << setw(6) << i;
			if (count % 5 == 0)
			{
				cout << endl;
			}
		}
	}
	cout << endl << "共计：" << count << "个" << endl;
}

int isPrime(int a)
{
	for (int i = 2; i < (int)(sqrt(a)); i++)
	{
		if (a%i == 0)
		{
			return 0;
		}
	}
	return 1;
}
           

以下为运行结果，共计186个：

三、水仙花数

（1）什么叫水仙花数？

水仙花数是指一个 n 位数（n≥3 ），它的每个位上的数字的 n 次幂之和等于它本身（例如：1^3 + 5^3+ 3^3 = 153）。

水仙花数只是自幂数的一种，严格来说3位数的3次幂数才称为水仙花数。

（2）关于求法

求法同上，暴力穷举。

（3）代码示例

void Nar()
{
	int sum,m,i;
	for (i = 100; i <= 1000; i++)
	{
		m = i;
		sum = 0;
		
		while (m)       //将数字逐位分解，并按水仙花概念相加
		{
			sum += pow((double)(m % 10),3);
			m /= 10;
		}
		
		if (sum == i)   
		{
			cout << i << '\t';
		}
	}
}
           

注意：

• pow函数原型：double pow (double _X , double _Y)
• 第一个参数为底数，第二个参数为指数
• 头文件：< cmath >

所以 pow((double)(m % 10),3) 中才需要将第一个参数转换,在这里将第二个参数转换也是可以的: pow( m % 10 ,3.0).

四、完数

（1）什么叫完数

完数，即完美数，一个数如果恰好等于除它本身外的因子之和，这个数就称为完数。例如6=1＋2＋3.(6的因子是1,2,3)

另外与完数相关的还有亏数与盈数

• 当一个自然数的所有真因子的和小于该自然数，那么该自然数便是亏数。
• 当一个自然数的所有真因子的和大于该自然数，那么该自然数便是盈数。

（2）方法

只需找出数字的各个因子，相加后判断是否与原来的数相等即可。

（3）代码示例

int perfect(int a)
{
	int i, sum = 0;
	for (i = 1; i < a; i++)
	{	
		if (a / i * i == a)
		{
			sum += i;
		}
	}
	if (sum == a)
	{
		return 1;
	}
	return 0;
}
           

五、回文数

（1）回文数

回文数(或回文数)是指一个像14641这样“对称”的数，即：将这个数的数字按相反的顺序重新排列后，所得到的数和原来的数一样。

（2）做法

将这个数逆序后的数与逆序前的数作比较，即核心部分是将数字逆序。

（3）代码示例

下列代码的作用是找出一定范围内的回文数

void symm(int a, int b)
{
	int i,m,sum;
	for (i = a; i <= b; i++)
	{
		m = i;
		sum = 0;
		
		while (m)  //核心算法
		{
			sum = sum * 10 + m % 10;
			m /= 10;
		}
		
		if (sum == i)
		{
			cout << i << " ";
		}
	}
}
           

注意：

1. sum记得在使用前要赋初始值，且sum赋初值的位置必须在内层循环前；
2. m 用来代替 原始数字 来完成逆序转换，如果不这样做，在完成逆序转换后原始数字将会变成0，无法进行比较。