gcd(最大公因数)

根据gcd性质：

(a,b)=(|a|,|b|)
(a,b)=(b,a)
(0,b)=|b|

由此可以将a,b推广至任意整数，且运算结果与顺序无关。
根据辗转相除法的思路，可以得到两个整数的gcd计算程序

int gcd(int a, int b)
{
	a = abs(a);
	b = abs(b);
	if (!(a % b)) return b;
	return gcd(b, a % b);
}

而对于计算多个整数的gcd时，有以下性质

若a1,a2,…,an是n个整数，则(a1,a2,…,an)=dn
其中有(a1,a2)=d2,(d2,a3)=d3,…,(d(n-1),an)=dn

由此可以写出计算n(n>=3)个数的gcd计算程序

int n_gcd(int* arr,int n)
{
	int dtemp = gcd(abs(arr[0]), abs(arr[1]));
	for (int i = 2; i < n; i++)
		dtemp = gcd(dtemp, abs(arr[i]));
	return dtemp;
}

lcm(最小公倍数)

tips:由于0不是任何整数的倍数，当进行lcm计算时，应当核验并预先假定这些整数中没有0。

根据lcm性质

[a,b]=[|a|,|b|]
[a,b]=a*b/(a,b)
由[b,a]=b*a/(b,a)且b*a=a*b,(a,b)=(b,a)
可得
[a,b]=[b,a]

由此可以将a,b推广至除0以外的任意整数，且运算结果与顺序无关。
可以得到两个整数的lcm计算程序：

int lcm(int a, int b)
{
	a = abs(a);
	b = abs(b);
	return a * (b / gcd(a, b));//先计算除法可防止计算中途发生溢出
}

而对于计算多个整数的lcm时，有以下性质

若a1,a2,…,an是n个整数，则[a1,a2,…,an]=mn
其中[a1,a2]=m2,[m2,a3]=m3,…,[m(n-1),an]=mn

由此可以写出计算n(n>=3)个数的lcm计算程序

int n_lcm(int* arr,int n)
{
	int dtemp = lcm(abs(arr[0]), abs(arr[1]));
	for (int i = 2; i < n; i++)
		dtemp = lcm(dtemp, abs(arr[i]));
	return dtemp;
}

Eratosthenes筛法(埃筛法)

基本思想

给定一个正整数N，把不超过N的一切整数按顺序排列，依次划去已找到的那个质数的所有不超过N的倍数，完成后留下来的即是质数。

tips:根据定理

设a是任一大于1的整数，则a的除1外最小正因数q是一质数，并且当a是合数时$q\le \sqrt{a}$。

可得知

要求出不超过N的一切质数，只需要把不超过$\sqrt{a}$的质数的倍数划去即可，因为不超过N的合数的最小质因数总是不超过$\sqrt{a}$的。

由以上定理和思想可写出埃筛法求质数的计算程序

int* Eratosthenes(long long n)
{
	char* arr = (char*)calloc(n+1, sizeof(char));
	int k;
	int* res = (int*)malloc(sizeof(int) * n);
	for (int i = 2; i <= sqrt(n); i++)
	{
		k = 2;
		if (arr[i] == 0x1)
			continue;
		while (i * k <= n)
		{
			arr[i * k] = 0x1;
			k++;
		}
	}
	int count = 0;
	for (int i = 2; i <= n; i++)
	{
		if (arr[i] == 0x0)
			res[++count] = i;
	}
	res[0] = count;
	free(arr);
	arr = NULL;
	res = (int*)realloc(res,sizeof(int)*(count+1));
	return res;
}

返回数组的数据格式为：res[0]为质数个数，res[1]~res[res[0]]为求得的质数

算数基本定理

任一大于1的整数能表成质数的乘积，即任一大于1的整数。

由算数基本定理可得到

任一大于1的整数的标准分解式

任一大于1的整数a能唯一地写成 $a=p_{{}_1}^{\alpha 1}{p}_2^{\alpha 2}...p_k^{\alpha k}$ 其中
${\alpha }_i>0i=1,2,...,k。且p_i<p_j(i<j)$ 。

$a=p_{{}_1}^{\alpha 1}{p}_2^{\alpha 2}...p_k^{\alpha k}$

此式称为标准分解式。
求任一大于1的整数的标准分解式的求解过程只能通过质数表从小到大进行构造，可得标准分解式计算程序

int* standard_factorization(long long n)
{
	int* primenums = Eratosthenes(100);
	int* res = (int*)malloc(sizeof(int) *200);
	int count = 0;
	for (int i = 1; i <= primenums[0]&&primenums[i]<=n; i++)
	{
		while (n % primenums[i] == 0)
		{
			res[++count]=primenums[i];
			n /= primenums[i];
		}
	}
	res[0] = count;
	res=(int*)realloc(res, sizeof(int)*(count+1));
	free(primenums);
	primenums = NULL;
	return res;
}

返回数组的数据格式为：res[0]为分解的质数个数，res[1]~res[res[0]]为分解结果，即res[1]*…*res[res[0]]为n的标准分解式。

n!的标准分解式

对于特殊的一种情况，求解n!时有以下性质

$n!={\prod }_{p⩽n}{p}^{{\sum }_{r=1}^{\infty }[\frac{n}{p^r}]}$

可写出计算程序

int* standard_factorization_fac(long long n)
{
	int* primenums = Eratosthenes(100);
	int* res = (int*)malloc(sizeof(int) * 200);
	int count = 0,k=1,sum=0,temp=n,i;
	while (temp)
	{
		temp >>= 1;
		sum += temp;
	}
	res[k] = primenums[1];
	res[k + 1] = sum;
	k += 2;
	for (i = 2; i <= primenums[0]&& primenums[i] <= n; i++)
	{
		temp = n; sum = 0;
		while (temp)
		{
			temp /= primenums[i];
			sum += temp;
				
		}
		res[k] = primenums[i];
		res[k + 1] = sum;
		k += 2;
	}
	res[0] = (i-1)*2;
	return res;
}

返回数组数据格式为,res[0]为组数个数，res[1]与res[2]为第一组，res[i]为底数，res[i+1]为指数。即n!=res[1]^res[2]*…*res[i]^res[i+1]。