L1-006 连续因子(Java)

本文介绍: 天梯赛练习题

题目

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

输入格式：
输入在一行中给出一个正整数 N（1<N<231）。

输出格式：
首先在第 1 行输出最长连续因子的个数；然后在第 2 行中按因子1因子2……*因子k 的格式输出最小的连续因子序列，其中因子按递增顺序输出，1 不算在内。

输入样例：
630
输出样例：
3
5*6*7

解题思路

理解连续因子的概念：连续因子意味着我们要找到一串相邻的整数，它们的乘积等于给定的N。
确定遍历的范围：因为连续因子序列的乘积等于N，所以序列的起始数字不需要超过√N。如果起始数字大于√N，则其乘积必然超过N。
遍历可能的连续因子序列：从2开始，尝试所有可能的起始数字，计算连续的乘积，直到乘积超过N。如果在某点乘积等于N，我们就找到了一个有效的因子序列。
记录最长序列：在遍历过程中，需要记录找到的最长的因子序列。如果找到了更长的序列，就更新这个记录。
输出结果：最后输出最长连续因子序列的长度和序列本身

解题过程中所遇到的问题

序列的起始数字不需要超过√N。如果起始数字大于√N，则其乘积必然超过N：这是可以让循环数少一半。降低了时间复杂度。

代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   //输入所求的数字
        int count = 0;    //计数器
        int start = 0;    //标记起始位置
        int max_count = 0;   //最大的因子个数
        for(int i = 2; i <= Math.sqrt(N); i++) { // 超过根号不可能有两个连续因子
            count = 0;
            //t和j都是临时的，只用来计算
            int t = N;
            int j = i;
            //相当于从2开始尝试除，如果整除，则2+1，并且次数+1，那就是除以3了，以此类推，不整除时就退出
            while(t % j == 0) {
                t = t / j;
                j++;
                count++;
            }
            //现有的次数与最大的次数相比，如果大于的话，则把能整除的开头给start，并且它变为最大次数
            if(count > max_count) {
                start = i;
                max_count = count;
            }
        }
        if(max_count != 0) {
            System.out.println(max_count);
            //i必须从0开始，因为下边要用到start+i
            for(int i = 0; i < max_count; i++) {
                System.out.printf("%d", start + i);
                //判断是否为最后一个数
                if(i != max_count - 1)
                    System.out.printf("*");
            }
        }
        else{
            //如果最大次数为空，则为素数，题目不算1，所以直接打印本身
            System.out.printf("%dn%d", 1, N);
        }
    }
}