递归分解质因数c程序

⑴ 用java编程 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。

将一个正复整数分解质因数。制例如:输入60；打印出2*3*5*2

算法实现构思:

1、用Scanner实现输入一个正整数n

2、用一个for循环遍历一个从 k=2开始查找到k<=n的数

3、如果 n%k==0的时候，输出k的值

4、然后把n的值递归一下，即 n=n/k

5、这个时候要把for循环重新执行，即再定义k=2

下面是实现代码：

上面是后来整理的构思以及代码实现，一开始拿到这个题目，就立马去做了，可是马上掉进了各种各样的坑，我觉得以后做算法题先把做题思路想好，从部分到整体，不然一道简单的算法题就要耗掉很多时间。

⑵ C语言编写：求2-100中，每个数的质因子

#include <stdio.h>
#include <math.h>

void fun(int num) /* 该函数输出num的因数分解表达式 */
{
int flag = 0 ; /* flag 表示找到了num的一个质因数 */
int i;
int have_factor=0; /* have_factor 表示num有没有质因数 */
int root;

do
{
flag=0;
root = sqrt(num); /* root 表示查找num的质因数的最大可能值 */
for(i=2;i<=root;i++)
{
if(num%i==0) /* 找到了num的一个质因数 */
{
if(have_factor==0) { printf("\n%d = %d * ",num,i); }
else { printf("%d * ",i); }
num/=i;
flag=1;
have_factor=1;
break;
}
}
}while(flag==1); /* 如果num还能继续分解，则继续循环，否则退出循环 */

if(have_factor==1) { printf("%d",num); }
else { printf("\n\n%d is a prime number!\n",num);}

return;
}

main()
{
int k;
for(k=2;k<=100;k++)
{
fun(k);
}

getch();
}

⑶ 用JAVA中递归思想编写程序：分解质因数例如90=2×3×3×5

按照自你的要求编写的Java程序如下：

importjava.util.Scanner;
publicclassCCT{
publicstaticvoidf(intn,intm){
inti=2;
if(n<2)return;
while(!(n%i==0)){
i++;
}
if(m==1)System.out.print(i);
elseSystem.out.print("*"+i);
f(n/i,m-1);
return;
}
publicstaticvoidmain(String[]args){
Scannersc=newScanner(System.in);
intn=sc.nextInt();
System.out.print(n+"=");
f(n,1);
System.out.println();
}
}

运行结果：

90
90=2*3*3*5