藍橋杯 因式分解

問題描述

　　設計算法，使用者輸入合數，程式輸出若個素數的乘積。例如，輸入6，輸出2*3。輸入20，輸出2*2*5。

資料規模和約定

　　輸入資料中每一個數在int表示範圍内。

思路

先求出2~n的所有素數，再進行分解

求素數的方法

代碼

#include<iostream>
using namespace std;

int len;
int prime[];//1~n的所有素數 
int a[];//輔助數組 
//遞歸分解
string fun(int n,int prime[]){
    if(n==) return "";
    for(int i=;i<=len;i++){
        if(n%prime[i]==){
            cout<<prime[i];
            if(n/prime[i]!=)
                cout<<"*";
            return fun(n/prime[i],prime);
        }
    }   
}

int main(){
    int n;
    cin>n;
    for(int i=;i<=n;i++){
        a[i]=;
    }
    for(int i=;i*i<=n;i++){
        if(a[i]==){
            for(int j=i*;j<=n;j++){
                if(j%i==) a[j]=;
            }
        }   
    }
    int j=;
    for(int i=;i<=n;i++){
        if(a[i]==) prime[j++]=i;   
    }
    len=j--;
    fun(n,prime);
    return ;
}