1210:因子分解
麦兜 / 2019-08-16 / 算法 / 阅读量 27065

题目

1210:因子分解
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3307 通过数: 2025
【题目描述】

输入一个数,输出其素因子分解表达式。
【输入】

输入一个整数 n (2≤n<100)。
【输出】

输出该整数的因子分解表达式。

表达式中各个素数从小到大排列。(幂次方不算 比如:3^2*5 也是正确)

如果该整数可以分解出因子a的b次方,当b大于1时,写做 a^b ;当b等于1时,则直接写成a。

【输入样例】

60

【输出样例】

2^2*3*5

【来源】

No

代码

#include<iostream>
using namespace std;
int arr[101];
void dfs(int n,int i)
{
    if (i > n || n == 1)  /*边界 因子不包括1 因子不能大于本身*/
            return;
        while (n%i == 0) /*能整除的才是因子*/
        {
            arr[i]++;   /*桶排序记录下来 方便输出幂次方*/
            n = n / i;
        }
        dfs(n, i + 1);/* i这个 因子不能除了 就让i+1 去试*/
}
int main()
{
    int n;
    cin >> n;
    dfs(n,2);
    bool f = false;
    for (int i = 0; i < 101; i++)
    {
        if (arr[i] && f)
        {
            cout << "*";
        }
        if (arr[i] > 0)
        {
            f = true;
        }
        if (arr[i] == 1)
            cout << i;
        else if (arr[i] > 1)
        {
            cout << i << "^"<<arr[i];
        }
    }
}

发表留言

人生在世,错别字在所难免,无需纠正。