Among all the factors of a positive integer $N$, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive $N,$ you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
Each input file contains one test case, which gives the integer $N (1<N<2^{31})$.
For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*...*factor[k]
, where the factors are listed in increasing order, and 1 is NOT included.
630
3
5*6*7
对于一个正整数$N$的所有因数,可能存在有连续的因数。例如,630可以分解为3×5×6×7,其中5, 6, 7是三个连续的数字。现给出任意一个正整数$N$,请你找出这个数最长的连续因数个数,并且输出最小的连续因数序列。
其中,第一行打印连续因数的最大个数。第二行以升序打印最小的连续因数序列,格式为 factor[1]*factor[2]*...*factor[k]
,不包含1。
本题 20 分,难度主要在理解题意。需要注意的几点,①连续因数序列有可能只有一个值;②对于素数来说,连续因数只有1个,值为它本身;③连续因数只要相乘是这个数分解的一部分就可以,也就是说连续因数的乘积可以整除该数即可。
以下为几个测试样点(来自《算法笔记》)
// 2
1
2
// 4
1
2
// 6
2
2*3
// 8
1
2
// 14
1
2
from math import sqrt
number = int(input())
max_n = int(sqrt(number)) + 1
result = []
for a in range(2, max_n+1):
product = 1
for b in range(a, max_n+1):
product *= b
if number % product:
break
else:
result.append((b-a+1, a, b))
if len(result):
length, start, end = sorted(result, key=lambda x: (-x[0], x[1]))[0]
print(length)
print('*'.join(map(str, [i for i in range(start, end+1) ])))
else:
print('1\n{}'.format(number))
https://segmentfault.com/a/1190000037690030
https://blog.csdn.net/xyt8023y/article/details/47756681
https://www.liuchuo.net/archives/2110