PAT A1096:Consecutive Factors(质因数分解)

题目内容

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.

Input Specification:

Each input file contains one test case, which gives the integer $N (1<N<2^{31})$.

Output Specification:

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.

Sample Input:

630

Sample Output:

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

AC 源代码

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