7-6 连续因子

港控/mmm° 2024-03-31 09:36 85阅读 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  
5*6*7

### 我的算法 ###

// 我的算法又长又难以理解

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

**运行结果**：  
![在这里插入图片描述][f90c5eb521e44caeb6c855931cb94c73.png]

[f90c5eb521e44caeb6c855931cb94c73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b9515439fa3840629ac785120119d4bb.png