7-6 连续因子
题目
7-6 连续因子 (20 分)
一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。
输入格式：
输入在一行中给出一个正整数 N（1<N<2^31）。
输出格式：
首先在第 1 行输出最长连续因子的个数；然后在第 2 行中按 因子1因子2……*因子k 的格式输出最小的连续因子序列，其中因子按递增顺序输出，1 不算在内。
输入样例：
630
输出样例：
3
567
我的算法
// 我的算法又长又难以理解
#include<stdio.h> #include<math.h> int main(void) { int n, i, j, k = 0, t = 0, flag = 0; int index = 0; int max = 0, cnt = 1; int cnt2 = 0; int a[200]; int b[100][100]; int c[10000] = {0}; scanf ("%d", &n); int m = sqrt (n), temp = n; for (i = 2; i <= m; i++) { if (temp % i == 0) { break; } } if (i > m) { flag = 1; } if (flag) { max = 1; a[0] = n; cnt = 1; printf ("%d\n%d\n", max, n); } else { for (i = 2; i <= m + 1; i++) { t = 0; if (temp % i == 0) { b[k][t] = i; t++; temp /= i; cnt = 1; for (j = i + 1; j <= m + 1; j++) { if (temp % j == 0 && temp != 0) { b[k][t] = j; t++; temp /= j; cnt++; } else { c[k] = cnt; k++; temp = n; break; } } } } for (i = 0; c[i] != 0; i++) { if (i == 0) { max = c[0]; } if (max < c[i]) { max = c[i]; index = i; } } printf ("%d\n", max); for (i = 0; i < max; i++) { printf ("%d", b[index][i]); if (i < max - 1) { putchar ('*'); } } } return 0; }
好的算法
#include <iostream> #include <cmath> using namespace std; int main() { long long n,m,i,j,k,sum = 0,num; //int会爆掉 cin >> n; m = sqrt(n); for(i = 2;i <= m; i++) // 需要计算的范围就是i到n的根号 { k = n; // 备份原来的数 for(j = i; k % j == 0; j++) // 计算连续了几次 { k /= j; } if(j - i > sum) { sum = j - i; // 连续的次数 num = i; // 从多少开始连续的 } } if(sum == 0) { sum = 1; // 输入的数字是质数的时候的情况 num = n; } cout<< sum << endl; for(int i = num; i < num + sum; i++) { if (i != num) putchar('*'); cout << i; return 0; }
运行结果：
