[数据结构与算法]用C语言编写长整型数分解质因数算法及优化算法执行时间

????????最近闲来无事，于是便随手编了一个分解质因数的算法。在编写好最初的程序之后（下面第一个程序），随手输入了自己的身份证号码打算让他分解因数，结果运行了900多秒才算出来（菜鸡一个），于是便有了后面优化该算法的过程。最后优化的效果还算比较满意，故来给大家分享一下。

????????这是我最初开始写的代码，思路很简单，先是定义了一个判断是否为质数的函数Is_prime()，然后又定义了一个因数分解函数prime_fact()，通过判断n是否位质数来执行while循环，如果不是质数，则执行循环，然后从2开始一个一个试，看能否整除n，能整除则打印i，同时n变成n/i；否则i自增1，直到n为质数。(为了直观，用了clock()函数输出代码的运行时间，函数头文件是time.h)

#include<stdbool.h>
#include<math.h>
#include<stdio.h>
#include<time.h>
typedef long long ll;

bool Is_prime(ll n)
{
	if (n <= 1) return false;
	ll t = (ll)(sqrt(n) + 0.5);
	for (ll i = 2; i <= t; i++)
		if (n % i == 0) return false;
	return true;
}

void prime_fact(ll n)
{
	if (n <= 1)
	{
		printf("%lld\n", n);
		return;
	}
	ll i = 2;
	while (!Is_prime(n))
	{
		if (n % i == 0)
		{
			printf("%lld×", i);
			n = n / i;
		}
		else i++;
	}
	printf("%lld\n", n);
}

int main()
{
	ll n;
	int t1, t2;
	scanf("%lld", &n);
	t1 = clock();
	prime_fact(n);
	t2 = clock();
	printf("执行时间:%.4lfs\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
	return 0;
}

随便输入一个数字：112233445566778899

结果就运行了70秒，，，

112233445566778899
3×3×11×83×102241×133593067
执行时间:70.7330s

我在优化代码之前先把prime_fact()输出的格式改了一下，有重复的因数就把它改成指数形式，形如a^N1×b^N2×...

void prime_fact(ll n)
{
	if (n <= 1)
	{
		printf("%lld\n", n);
		return;
	}
	ll i = 2, tmp = 1;
	int N = 1;
	while (!Is_prime(n))
	{
		if (n % i == 0)
		{
			if (i == tmp) N++;
			n = n / i;
			tmp = i;
			if (n % i)
			{
				if (N == 1) printf("%lld×", i);
				else printf("%lld^%d×", i, N);
				N = 1;
			}
		}
		else i++;
	}
	if (n == tmp) printf("%lld^%d\n", n, N + 1);
	else printf("%lld\n", n);
}

结果如图(运算效率嘛，，，)

112233445566778899
3^2×11×83×102241×133593067
执行时间:70.8610s

????????代码运行慢的原因是每次循环过后都要先判断n是否为质数，而while循环的次数越多，运行就越慢，所以我先从判断质数这个函数开始优化。由于每次求出一个因数i之后，n变成了n/i，此时的n肯定不会再被比上一个求出的因数i小的数整除，所以说判断质数可以不用每次从2开始判断，而是从最新算出的因数开始，这样会节省很多时间。这样判断质数的函数就要多用一个参数，作用是从这个数来判断是否为质数。由于质数除了2是偶数，其余都是奇数，所以从3开始i自增2。优化后的代码如下：

bool Is_prime(ll n, ll m)       //n是要判断的整数,m指因数从m开始
{
	if (n <= 1) return false;
	m = (m < 2) ? 2 : m;        //m最小从2开始
	ll t = (ll)(sqrt(n) + 0.5);
	for (ll i = m; i <= t; i += 1 + i % 2)
		if (n % i == 0) return false;
	return true;
}

void prime_fact(ll n)
{
	if (n <= 1)
	{
		printf("%lld\n", n);
		return;
	}
	ll i = 2, tmp = 1;
	int N = 1;
	while (!Is_prime(n, i))
	{
		if (n % i == 0)
		{
			if (i == tmp) N++;
			n = n / i;
			tmp = i;

			if (n % i)
			{
				if (N == 1) printf("%lld×", i);
				else printf("%lld^%d×", i, N);
				N = 1;
			}
		}
		else i += 1 + i % 2;        //i除了2，其余都是奇数
	}

	if (n == tmp) printf("%lld^%d\n", n, N + 1);
	else printf("%lld\n", n);
}

运行结果：看样子是提高了不少，但还是有点慢。(这效率还不如把while循环的条件改为n!=1，不判断质数)

112233445566778899
3^2×11×83×102241×133593067
执行时间:9.3950s

????????但是分解我的身份证号码的时间还是很长(200s左右)，即使把循环条件换成n!=1，也要运行15秒左右。难道用质数当循环条件就没一点用处？

???????可以看这个数：188467733573690487(=3×7×41×53681×4077681107)，循环条件用质数判断反而比把循环条件换成n!=1运行的还要快！？为什么。

? ? ? ?在我一番仔细分析后发现，循环条件用质数判断的话，执行时间是与分解后第二大的质因数成正比(因为循环变量i从2到第二大的质因数就停止了)，而循环条件换成n!=1，执行时间是与分解后最大的质因数成正比(因为循环变量i从2到最大的质因数)，虽然判断质数的时间肯定比判断n!=1的时间慢，但是当分解出来的最大质数远大于第二大质数时候(4077681107>>53681)，情况就逆转了。

???????所以还能不能对算法进行改进？如果质数判断慢那就减少循环次数，这样不就减少了判断的次数？考虑到每次判断质数的时候，如果这个数是合数，那么判断语句的循环变量不就是这个合数的一个因数？不正好是分解质因数时候要用到的那个数字嘛。所以可以保存这个数，并将这个数直接赋值分解质因数的循环变量，这样不就减少了大量的循环次数？直接上代码和结果：

#include<stdlib.h>                  //引入malloc头文件
bool Is_prime(ll n, ll m, ll* i)    //n是要判断的整数,m指因数从m开始
{                                   //*i用来保存能够整除n的最小值
	if (n <= 1) return false;
	m = (m < 2) ? 2 : m;            //m最小从2开始
	ll t = (ll)(sqrt(n) + 0.5);

	for (*i = m; *i <= t; *i += 1 + *i % 2)
		if (n % *i == 0) return false;
	return true;
}

void prime_fact(ll n)
{
	if (n <= 1)
	{
		printf("%lld\n", n);
		return;
	}
	ll i = 2, tmp = 1, * j = (ll*)malloc(sizeof(ll));    //tmp用来保存上一个质因数
	int N = 1;
	while (!Is_prime(n, i, j))
	{
		i = *j;           //i从判断素数时候保存在*j的值开始
		if (n % i == 0)
		{
			if (i == tmp) N++;
			n = n / i;
			tmp = i;
			if (n % i)
			{
				if (N == 1) printf("%lld×", i);
				else printf("%lld^%d×", i, N);
				N = 1;
			}
		}
		else i += 1 + i % 2;      //i除了2，其余都是奇数
	}
	if (n == tmp) printf("%lld^%d\n", n, N + 1);
	else printf("%lld\n", n);
}

????????可以看出执行效率提高了很多，上面测试的数大部分都在瞬间完成了，但是当这个数为质数且比较大的时候，执行的效果还是有点慢，就要10秒多了，，，

112233445566778899
3^2×11×83×102241×133593067
执行时间:0.0000s
188467733573690487
3×7×41×53681×4077681107
执行时间:0.0010s
9223372036854775783
9223372036854775783
执行时间:12.3810s

????????最终下来，程序的时间复杂度最好的情况是合数且分解出来的每个质因数非常接近甚至相等(分解出来的最大质因数尽量最小)，几乎为O(1)。最坏情况就是这个数为质数，时间复杂度就是判断这个数是质数的时间复杂度，为O(sqrt(n))。所以我觉得最后能改进的地方也就剩下判断质数的函数了。本人水平有限也只能优化到这了，，，各位大佬见谅

? ? ? ? 最后贴上完整代码，并将有符号长整型改成了无符号长整形：

#include<stdbool.h>
#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
typedef unsigned long long ll;
bool Is_prime(ll n, ll m, ll* i)    //n是要判断的整数,m指因数从m开始
{                                   //*i用来保存能够整除n的最小值
	if (n <= 1) return false;
	m = (m < 2) ? 2 : m;            //m最小从2开始
	ll t = (ll)(sqrt(n) + 0.5);

	for (*i = m; *i <= t; *i += 1 + *i % 2)
		if (n % *i == 0) return false;
	return true;
}

void prime_fact(ll n)
{
	if (n <= 1)
	{
		printf("%llu\n", n);
		return;
	}
	ll i = 2, tmp = 1, * j = (ll*)malloc(sizeof(ll));    //tmp用来保存上一个质因数
	int N = 1;
	while (!Is_prime(n, i, j))
	{
		i = *j;           //i从判断素数时候保存在*j的值开始
		if (n % i == 0)
		{
			if (i == tmp) N++;
			n = n / i;
			tmp = i;
			if (n % i)
			{
				if (N == 1) printf("%llu×", i);
				else printf("%llu^%u×", i, N);
				N = 1;
			}
		}
		else i += 1 + i % 2;      //i除了2，其余都是奇数
	}

	if (n == tmp) printf("%llu^%u\n", n, N + 1);
	else printf("%llu\n", n);
}

int main()
{
	ll n;
	int t1, t2;
	while (scanf("%llu", &n) != EOF && n)
	{
		t1 = clock();
		prime_fact(n);
		t2 = clock();
		printf("执行时间:%.4lfs\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
	}
	return 0;
}

输入了一下无符号长整形范围内最大的质数18446744073709551557

结果如下：

18446744073709551557
18446744073709551557
执行时间:13.9960s

所以理论上这个程序在无符号长整形数的范围内需要的最长时间为14s左右(因机器而异)，只能说勉强能用。如果有更好地改进建议欢迎大家分享~