蓝桥杯 因式分解

问题描述

　　设计算法，用户输入合数，程序输出若个素数的乘积。例如，输入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 ;
}