分解质因数（数学）

文章目录

• ​​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()