menu Error0 Blog
1210:因子分解
27026 浏览 | 2019-08-16 | 分类:算法 | 标签:

题目

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];
        }
    }
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89