分解质因数（数学）

分解质因数（数学）

文章目录

​​Question​​​​Ideas​​​​Code​​

Question

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式 第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式 对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围 1≤n≤100, 2≤ai≤2×109 输入样例： 2 6 8 输出样例： 2 1 3 1

2 3

Ideas

试除法分解质因数 需要注意 只有大于2的自然数才可以

每个大于1的自然数，若不是本身就是质数，就可写为2个以上的质数的积,而且这些质因子按大小排列之后，写法仅有一种方式

Code

# 试除法分解质因数 O(sqrt(N) 比试除法求质数快n = int(input())def divide(x): for i in range(2,int(x**0.5)+1): if x % i == 0: s = 0 while x % i == 0: x //= i s += 1 print(i,s) if x > 1: print(x,1) for i in range(n): divide(int(input())) print()

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。