#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的因数分解式,按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格

【解题思路】

本题主要考察素因数相关算法的知识。

  1. 输入一个数字,设置一个输出列表factors。
  2. 设定一个判断素数的函数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.