PTA --- L1-006 连续因子

题目地址

一个正整数

输入格式：

输入在一行中给出一个正整数

输出格式：

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

输入样例：

输出样例：

思路：

首先，题目求的是 最长连续因子的个数 + 升序排序的连续因子的序列

由题目，数据的范围是 2~ 2^30 -1，可以借此推算得到序列的最长长度

#include<stdio.h>
int main(){
    int u =2;
    for(int i = 1;i< 30;i++){
        u = u *2;
    }
    int sum = 1;
    for(int i = 1;i < 15;i++)
    {
        sum = sum * i;
        if(sum >= u){
            printf("%d %d
",i,sum);
            break;
        }
    }
    return 0;
}

可见，当序列的最长长度（1*2*3*4.....*12）时，所得值仍在数据范围之内，当继续乘到13时，超出数据的范围，可见，在数据范围内，整个序列的最大连续长度为12

而对于求一个数n的因子，只需要判定从 2 ~ √n 是否存在因数即可：

那么接下来就可以，从序列的最大长度12往下暴力循环{

　　每次循环内部都从2开始做为因数判定开始的数字，直到 √n{

　　　　针对因数判定开始的数字，往后连续乘当前循环判定的序列的长度的数字；
　　　　根据连续乘所得的数字判定是否是n的因子，如果是，则退出循环，否则继续；
　　}

}

最后根据因数判定开始的数字 + 序列的长度，输出连续的序列即可

为什么会得到 最长连续因子的个数？

因为是从最长的因子序列的长度（12）、最小的因子开始循环判定（2），保证了一旦发现有这样的序列的积是它的因子，那么这样的序列必然是最长的连续序列。

# 注解：为了达到最长的因子序列的目的，应使 4*5*6 ==> 2*3*4*5 。所以，可以由长度最大、序列开始因子最小开始暴力循环，进行寻找。

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll prd;
    int rootn=sqrt(n);//得到根号N 
    int flag=0,start,len;//定义是否为乘积因子的标识，乘积序列开始的因子，序列长度 
    for(len=12;len>=1;len--)//序列最长为12，递减到1 
    {
        for(start=2;start<=rootn;start++)//从当前一轮乘积因子的上界从2开始到根号N，注意一定是小于等于，否则有一个点会不过 
        {
            prd=1;
            for(int i=start;i<start+len;i++)//从当前乘积因子开始乘积，乘积len个长度 
            prd*=i;
            if(n%prd==0)//如果找到乘积因子 
            {
                flag=1;
                break;//标识，及时退出 
            }
        }
        if(flag)
        break;
    }
    if(!flag)//如果未标识为1，说明是质数 
    cout<<1<<endl<<n;
    else
    {
        cout<<len<<endl<<start;
        for(int i=start+1;i<start+len;i++)//输出，如果只有1个输出一个 
        cout<<'*'<<i;
    }
    return 0;
}