L1-6. 连续因子

L1-6. 连续因子

L1-6. 连续因子

一个正整数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）开始往前扫，不断更新维护最长连续因子的个数并保存最小的连续因子序列。

AC代码：

#include#include#include#includeusing namespace std;int main(){ int N,cnt=0,zhtai=1; int n=0; char a[1010]; char temp[1010]; int sq; scanf("%d",&N); sq=(int)sqrt(N)+1; //从该数的根号往前扫 for(int i=sq;i>=2&&zhtai;--i){ cnt=0; if(N%i==0){ temp[cnt++]=i; int t=N/i; for(int j=i-1;j>=2;--j) { if(t%j==0){ temp[cnt++]=j; t=t/j; if(j==2) { zhtai=0; } } else{ temp[cnt]=0; break; } } //不断更新连续因子的个数和保存连续因子 if(cnt>=n){ strcpy(a,temp); n=cnt; } } } if(n==0)printf("%d\n%d",1,N); else{ printf("%d\n",n); for(int j=n-1;j>=0;--j){ printf("%d",a[j]); if(j!=0){ printf("*"); } else{ printf("\n"); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。