【GPLT】L1-006 连续因子
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88615969
题目描述：
一个正整数 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解题思路：
连续因子最大值一定不会超过sqrt(N)，maxcnt是用来记录连续因子长度的，start为第一个连续因子的所在下标，用while语句来寻找最长连续因子。需要注意的是若输入的N是素数，则连续因子就是其本身，连续长度为1。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;
int cnt = 0, maxcnt = 0, start = 0; //maxcnt为连续因子长度,start为第一个连续因子
for(int i = 2; i <= sqrt(N); i++)
{
int temp = N;
cnt = 0;
int j = i;
while(temp%j == 0)
{
temp /= j++;
cnt++;
}
if(cnt > maxcnt) //更新连续因子长度
{
maxcnt = cnt;
start = i;
}
}
bool isVirgin = true; //判断是不是第一次
if(maxcnt == 0) //对于素数而言,连续因子就是其本身,连续长度为1
{
cout << 1 << endl << N;
}
else
{
cout << maxcnt << endl;
for (int i = 0; i < maxcnt; i++)
{
if(isVirgin)
{
cout << start+i;
isVirgin = false;
}
else
{
cout << "*" << start+i;
}
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-03-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录