test 6.1 分解质因数（5分）

每个非素数（合数）都可以写成几个素数（也可称为质数）相乘的形式，这几个素数就都叫做这个合数的质因数。比如，6可以被分解为2x3，而24可以被分解为2x2x2x3。

题目内容

每个非素数（合数）都可以写成几个素数（也可称为质数）相乘的形式，这几个素数就都叫做这个合数的质因数。比如，6可以被分解为2x3，而24可以被分解为2x2x2x3。

现在，你的程序要读入一个[2,100000]范围内的整数，然后输出它的质因数分解式；当读到的就是素数时，输出它本身。

提示：可以用一个函数来判断某数是否是素数。

输入格式

一个整数，范围在[2,100000]内。

输出格式

形如：
n=axbxcxd
或
n=n
所有的符号之间都没有空格，x是小写字母x。abcd这样的数字一定是从小到大排列的。

输入样例

18

输出样例

18=2x3x3

限制

时间限制：500ms 内存限制：32000kb

代码实现

C语言

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

//寻找并返回最小质因数，没有则返回0 
int isMinPreme(int n)
{
    int tmp = 0;
    for (int MinPreme = 2; MinPreme < sqrt(n) + 1; MinPreme++)
    {
        if (n % MinPreme == 0)
        {
            tmp = MinPreme;
            break;  //找到最小质因数立即跳出循环 
        }
    }
    return tmp; 
}

//短除法，除以最小质因数并打印，返回商 
int getQuotient(int n)
{
    int tmp = 0;

    int MinPreme = isMinPreme(n);
    //如果输入已经是2，已进行到最后一步，立即打印。 
    if (n == 2)
    {
        printf("%d", n);
    }
    //短除并输出 
    else if (MinPreme > 0)
    {
        printf("%dx", MinPreme);
        n /= MinPreme;
        tmp = n;
    }
    // 最小质因数为n本身 
    else
    {
        printf("%d", n);
    }

    return tmp;
}

int main()
{
    int n = 0;
    scanf("%d", &n);

    printf("%d=", n);   
    // 不断短除获得商，直到n=2 
    while (n > 1)
    {
        n = getQuotient(n);
    }

    return 0;
}