PAT A1096

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 356*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<231).

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
567

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "stdio.h"
#include "math.h"
//#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "algorithm"
using namespace std;
typedef long long LL;
int main(){
LL n;
scanf("%lld", &n);
//sqrt为根号N,ansLen为最长连续整数,ansI为对应的第一个整数
LL sqr = (int)sqrt(1.0*n), ansI, ansLen = 0;
for (LL i = 2; i <= sqr; i++) {
LL temp = 1, j = i;//temp为当前连续整数的乘积
while (1) {//让j从i开始不断加1,看最长能到多少
temp *= j;
if (n % temp != 0) {
break;//不可以整除,跳出
}
if (j - i + 1 > ansLen) {//发现了更长的长度
ansI = i;
ansLen = j - i + 1;
}
j++;
}
}
if (ansLen == 0) {//最大长度为0,说明根号n范围内没有解
printf("1\n%lld", n);//输出n本身
}else{
printf("%lld\n", ansLen);//输出最大长度
for (LL i = 0; i < ansLen ; i++) {
printf("%lld", ansI + i);
if (i < ansLen - 1) {
printf("*");
}
}
}
return 0;
}