记一次操蛋的代码debug与重构

今天计算导论与程序设计课上，老师留了这么个练习：

这道题老师给了一个额外要求：代码中不得出现哪怕一个循环，要求全部使用递归去做。
由于之前成功做出了带循环的这道题（代码如下）：

int isPrime(int n){
    int i;
    for(i=2;i《sqrt(n);i++)
        if(n%i==0)return 0;
    return 1;
}
void printFactor(int n,int b){
    if(b==1)printf("%d=",n);
    int i;
    int sign=0;
    for(i=2;i《n&&!sign;i++)
    {
        if((isPrime(i)==1)&&n%i==0)
        {
            sign=1;
            if(n==i)
            {
                printf("%d",i);
                if(b)printf("\n");
                return;
            }
            else
            {
                printf("%d*",i);
                printFactor(n/i,0);
            }
        }
    }
    if(!sign)printf("%d\n",n);
}

我窃喜这还不简单，只要把所有的循环改成递归就好了。经过一气操作，代码很快成型了：

int isPrime(int n,int num) {
	if(num==2)return 1;
	if((n==sqrt(num))||n+1==num)return num%n?1:0;
	if(num%n==0)return 0;
	if(isPrime(n+1,num)==0)return 0;
	else return 1;
}
void printFactor(int n,int b) {
	if(b==1)printf("%d=",n);
	if(!firstPrime(2,n,0,b))printf("%d\n",n);
}
int firstPrime(int i,int num,int sign,int b) {
	if(sign==1||i==num)return sign;
	if((isPrime(2,i)==1)&&num%i==0) {
		sign=1;
		if(num==i) {
			printf("%d",i);
			if(b)printf("\n");
			return sign;
		} else {
			printf("%d*",i);
			printFactor(num/i,0);
		}
	}
	firstPrime(i+1,num,sign,b);
}

没想到这个代码只拿了60pts，剩下的全T掉了。
我仔细一看，噢，第13行的
if(sign==1||i==num)
改成
if(sign==1||i==sqrt(num)+1)
不就能降低时间复杂度了！

在修改了其他细节问题之后，我又交了，没想到拿了80pts，有一个点TLE了。

我很疑惑：现在这代码复杂度降下来了，难道是三目运算符的原因？

上网继续搜索，发现三目运算符确实比if else慢了许多。把三目运算符改了之后提交，发现代码运行时长倒是降了几毫秒，但是那个点始终TLE。这下我整不会了，开始瞎改代码，发现不论如何，那个点都TLE。不知不觉一个多小时过去了，还是出错。真搞人心态。我越发觉得我的做法有问题。

这时ych路过，看过周姐的AC代码的ych吐槽我代码好长。于是我讨来周姐的AC代码，发现的确很简洁明了，肯定做法和我的不一样，于是我开始在纸上推算。

推着推着我发现，似乎任何一个合数都可以被分解为一个质数与另一个数的乘积……一直拆分下去，不就是算术基本定理吗？

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

我恍然大悟了：

我之前的做法是：比如要对num=105进行拆分，那么先判断i=2、3、4、5……是不是素数，也就是对每一个大于1的自然数判断它是否是质数。如果找到一个i，i既是素数又能被num整除（i=5），那么就得到了num的最小质因数i=5，令num=num/i之后，递归完成以上过程，直到完成拆分。

这种做法用循环倒是可以高速完成。但是在C语言里，用递归会产生巨大的开销。

比如要拆分一个巨大的num，而这个num的最小质因子又很大(把这个最小质因子设为z)，那么程序要判断2到z之间的所有数字是否为素数，这个庞大的过程用递归会伴随着大量的系统栈的push和pop操作，耗费大量时间。而题目中最多要判断100个num，假如100个num都很巨大，那么必然会造成运行超时。

可是如果用算术基本定理呢？

我们已经知道任何一个大于1的自然数num,如果num不为质数，那么num可以唯一分解成有限个质数的乘积。

进而可以得知，num除了1之外最小的因数肯定是一个素数，也就是num的最小质因数。

比如还是对num=105进行拆分，这回我们不需要判断i=2、3、4、5……是不是素数了，只需找到第一个能整除num的i（i=5)，那么这个i就是最小质因数，我们再递归上述过程，直到完成拆分。

完成上述思考之后，我急速重构了代码：

int f(int n,int num) {
	if(num%n==0) {
		if(num!=n)printf("%d*",n);
		else printf("%d\n",n);
		return num/n;
	}
	f(n+1,num);
}
void printFactor(int n,int b) {
	if(b==1)printf("%d=",n);
	if(n==1) {
		if(b==1)printf("1\n");
		return;
	}
	b=0;
	printFactor(f(2,n),b);
}

可见代码简洁明了了许多。虽然题目的测试数据强度还不够硬————假如num是一个巨大的素数（接近10万），递归次数过多（从2一路判断到num）会造成系统栈溢出，但是这个代码足以AC这道题啦！