7-6 连续因子

GeekLiHua

发布于 2025-01-21 14:47:17

8000

代码可运行

文章被收录于专栏：Java

运行总次数：0

代码可运行

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;
}

运行结果：