PTA天梯赛练习集-L1-006 连续因子 (20分)

缺乏、安全感 2022-12-25 00:56 179阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]  
暴力找因子，代码如下：

#include <iostream>
    #include <math.h>
    using namespace std;
    int main()
    {
        
    	int i,n;
    	int max=0,count,start=0;
    	cin>>n;
    	for(i=2;i<sqrt(n)+1;i++)
    	{
        
    		int k=n;
    		count=0;
    		int j=i;  
    		while(k%j==0) // 找连续的数
    		{
        
    			k=k/j;
    			j+=1;
    			count+=1;	
    		}
    		if(count>max)  // 从开头开始筛选连续的最多的，不加=是因为题目要求找最小的连续因子
    		{
        
    			max=count;
    			start=i;
    		}
    	}
    	
    	if(max==0) cout<<"1"<<endl<<n;
    	else
    	{
        
    		cout<<max<<endl;;
    		for(i=start;i<(start+max);i++)
    		{
        
    			cout<<i;
    			if(i!=(start+max-1)) cout<<"*";
    		}
    	}
    }

注意！！！  
1.如果是质数的话，第一行输出1第二行输出该数本身  
2. **i=2; i<sqrt(n)+1**  
这样判断是因为数N在【sqrt(N)，N】不可能存在连续因子，所以我们只需在【2，sqrt(N)】区间以不同的起始值，更新最终起始值(start)和连续因子长度(max)即可

另外一种方法  
从阶乘方面考虑（法二）：  
[法二][Link 1].

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0226d7fd29a6446e92a243ada5282762.png
[Link 1]: https://blog.csdn.net/qq_37701948/article/details/79960225/