首页 > 试题广场 >

Prime Factors (25)

[编程题]Prime Factors (25)

热度指数：8865 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *...*pm^km.

输入描述:

Each input file contains one test case which gives a positive integer N in the range of long int.

输出描述:

Factor N in the format N = p1^k1 * p2^k2 *...*pm^km, where pi's are prime factors of N in increasing order, and the exponent ki is the number of pi -- hence when there is only one pi, ki is 1 and must NOT be printed out.

示例1

输入

97532468

输出

97532468=2^2*11*17*101*1291

算法知识视频讲解

Python

初心者托奇

a = int(input())
d = {};m = [];b = a
while True:
    for i in range(2,int(a ** 0.5) + 1):
        if a / i == a // i:
            a /= i
            d[i] = d[i] + 1 if i in d else 1
            break
    else:
        d[int(a)] = d[int(a)] + 1 if int(a) in d else 1
        break
for i in sorted(d):
    m.append((str(i) + '^' + str(d[i])) if d[i] > 1 else str(i))
print(str(b) + '=' + '*'.join(m))

发表于 2020-02-19 14:33:01 回复(0)