PAT-A 真题 – 1096 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$\times$5$\times$6$\times$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
5*6*7

题目大意：给定一个数字，找到它最长、数字最小的连续因子，并输出。

这道题要注意因子的概念，比如120，最小最长的因子时2，3，4，5，而不是2，3，4，5，6！！！！！

之前认为只要能除尽的就算因子，所以就遍历了一遍，把能除尽的找出来，找到最长连续的输出，但是总有两个测试点共4分无法通过！

这道题最好的办法时遍历数字，然后构造连乘，找因子。

遍历全部数字会超时，只要遍历到sqrt(num)就好了，因为大于平方根的数字相乘肯定超过原来的数字了，肯定不是因子。

注意质数的判断！

代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
  int num;
  cin >> num;
  int max_len = 0, index = 0;
  for(int i = 2; i < sqrt(num); i++){
    int mult = 1, len = 0, idx = i;
    while(num % mult == 0 && mult <= num){
      mult *= (idx++);
      if(mult <= num && num % mult == 0) len++;
    }
    //printf("%d\t%d\t%d\n", len, mult, i);
    if(max_len < len)
      index = i, max_len = len;
    
  }
  //printf("%d\t%d\n", index, max_len);
  if(max_len == 0) cout << "1\n" << num;
  else{
    cout << max_len << endl;
    for(int i = index; i < index + max_len; i++){
      if(i != index) cout << '*';
      cout << i;
    }
  }
  return 0;
}