#4218. 因数分解(23-9五级)
因数分解(23-9五级)
因数分解
【问题描述】 每个正整数都可以分解成素数的乘积,例如:6=2×3、20=22 ×5。现在,给定一个正整数N,请按要求输出它的因数分解式。
【输入描述】
输入第一行,包含一个正整数N。约定
【输出描述】 输出一行,为N的因数分解式。要求按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格。
【样例输入1】
6
【样例输出1】
2*3
【样例输入2】
20
【样例输出2】
2^2*5
【题目大意】 输出N的因数分解式,按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格
【解题思路】
本题主要考察素因数相关算法的知识。
- 输入一个数字,设置一个输出列表factors。
- 设定一个判断素数的函数isPrime()。
3.如果是素数,将该数和数字1作为列表存入列表factors。
4.否则,遍历从2到input_number,如果i为input_number的因数,将该因数i
和数字0存入列表factors,使用唯一分解定理,找到素因数,将0增加1。当
因数不能整除时跳出while循环,判断该数是否素数,满足添加到列表中。
5.遍历factors列表,如果只出现1次,直接输出,否则换成指数形式输出
Limitation
1s, 1024KiB for each test case.