算法笔记_03:蓝桥杯练习 分解质因数

---

这是我第一次自己写的，思考的递归程序，看起来有些繁琐。

---

1. 问题描述

<blockquote>
　　将一个正整数N(N∈[1,32768])分解质因数，把质因数按从小到大的顺序输出。最后输出质因数的个数。
输入格式
　　一行，一个正整数
输出格式
　　两行，第一行为用空格分开的质因数
　　第二行为质因数的个数
样例输入
66
样例输出
2 3 113
样例输入
90
样例输出
2 3 3 5
4
样例输入
37
样例输出
37
1
</blockquote>
<p>

---

2. 解决方案

<pre> <big>
note1.起初我想用Set存，能到不重复的质因子，不满足题目要求。
note2.这道题，应用递归的方法。找入口，找出口。
note3.大神的c语言编写的代码，思想与我的有相通之处：
  他是先取得所有小于待分解数的质数，我是每次都从质数2开始找质因子，但我门都是要进行递归求质因数。
  <a href="#dest">分解质因数2</a>
note4.以整数举例画图，感觉类似图的深度搜索，待验证！！

分解90的质因数.png
</big></pre>
<u>实现java代码1</u>

import java.util.ArrayList;
import java.util.Scanner;

public class 分解质因数 {
    ArrayList<Integer> prime = new ArrayList<Integer>();    //存放质因数列表

    public boolean isPrime(int k) { //判断质数
        if (k == 1 || k == 0)
            return false;
        int i = 0;
        for (i = 2; i <= k / 2; i++) {
            if (k % i == 0)
                return false;
        }

        return true;
    }

    public ArrayList<Integer> divide(int num, int start) {  //num--当前待分解的数，start--最小的可最为因子的质数
        if (num == 1)           //递归出口：当为1，退到入口处
            return prime;

        if (num == 2) {
            prime.add(num);     //最小的待分解的数，可以直接加入，然后完成。
            // return prime;
        }

        for (int i = start; i < num; i++) {
            if (isPrime(num)) {     //如果待分解的数为质数，直接加入
                prime.add(num);
                return prime;       //递归出口：退到入口处
            } else {
                if (isPrime(i)) {
                    // System.out.println(i);
                    int temp = num % i;     //余数
                    if (temp == 0) {
                        prime.add(i);   //说明i为质因子，将i加入。
                        num = num / i;
                        if (num == i) {
                            prime.add(i);   //当存在num==i时，重复加入i；
                        } else {
                            divide(num, i);  //递归新的待分解的数
                            // prime.add(num);
                            return prime;
                        }

                    }
                }
            }
        }

        return prime;
    }

    public static void main(String[] args) {
        分解质因数 test = new 分解质因数();
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        /*
         * if(test.isPrime(m)) { System.out.println("ye"); }
         */
        // System.out.println(test.divide(m, 2).size());
        ArrayList<Integer> prime = test.divide(m, 2);
        for (int i = 0; i < prime.size(); i++) {
            System.out.print(prime.get(i) + " ");
        }
        System.out.println();
        System.out.println(prime.size());
    }
}

<p></p>
<u>实现C++代码<a name="dest">2</a></u>

#include<iostream>
#include<cmath>

using namespace std;

int zs[10001];
int k;

//递归求因数
string pri(int m){
    if(m==1) return "";
    for(int i=0;i<k;i++){
        if(m%zs[i]==0){
            cout<<zs[i];
            if(m/zs[i]!=1) cout<<"*";
            return pri(m/zs[i]);
        }
    }
}

//筛选出质数
void zhishu(int a,int b){
    int i,j;
    k=0;
    for(i=2;i<=b;i++){
        int s=sqrt(i);
        for(j=2;j<=s;j++)
            if(i%j==0) break;
        if(j>s){
            zs[k]=i;
            k++;
        }
    }
}

int main(){
    int a,b;
    cin>>a>>b;
    zhishu(a,b);
    for(int i=a;i<=b;i++){
        cout<<i<<"=";
        pri(i);
        cout<<endl;
    }
    return 0;
}