题目描述

埃迪的兴趣非常广泛，最近他对素数很感兴趣。艾迪发现所有拥有的数字都可以被分解成素数的乘法，但他不会写程序，所以艾迪不得不请聪明的你帮他，他让你写一个程序，可以把数字分解成素数因子的乘法。

输入每行包含一个数字1 < x <= 65535，表示集合的元素数。

您必须在输出中为每个条目打印一行，其中包含上一个问题的答案。

样例

11
9412

11
2213*181

算法

利用欧拉函数把一个数进行素数分解
满足的并进行储存

C++ 代码

#include<iostream>
using namespace std;


int a[1000];
int i,j,l,n;

void divide(int x) {

    for(i = 2,j = 0; i*i <= x; i++) {//从小到大遍历x的因数

        if(x % i == 0) {
            x = x/i;
            a[j++] = i;
            while(x % i == 0) {//i是x的因数
                x = x / i;
                a[j++] = i;
            }
        }

    }

    if (x > 1) a[j++] = x;

}



int main() {

    while(cin >> n) {

        divide(n);

        for(l=0,i=0; i < j; i++) {
            if(l==0) {
                cout << a[i];
                l++;
            } else  cout << "*" << a[i];
        }

        cout << endl;

    }

    return 0;
}