1998-c-二

东北大学842考研

算法思想: 输入一个数x，将其对n取余(n从2开始)，如果余数为零，m=m/n,重复操作。如果余数不为零，n++,直到找到能够被其整除的数。

非递归算法

#include <stdio.h>
int main()
{
    int n, i, c;//需要分解的自然数 
    scanf("%d", &n);
    i = 2; c = n;
    printf("%d=", n);
    while(n != 1)
    {
        if(n%i == 0) {
            printf("%s%d", c == n ? "" : "*", i);
            n /= i;
        } else ++i;
    }
    
}

递归算法实现

#include <stdio.h>

void num_break(int c,int n,int i)
{
	
	if(n!=1)//n==1,证明分解完毕 
	{
		if(n%i==0)
		{
			printf("%s%d", c == n ? "" : "*", i);
			n/=i;
			num_break(c,n,i);
		}	
		else
			num_break(c,n,++i);
	}
 } 

int main()
{
	num_break(140,140,2); 
    
}