一个正整数 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
- ------------------------------------------------L1-006----------------------------------------------------------
注解: 这道题才是我今天要着重讲一下滴~ 一上来懵了一下, 突然不知道怎么处理因式分解, 一开始的思路就是一个 for 循环从头一直除到尾, 结果发现样例都过不了, 这种题跟很早我在说想要研究的因式分解题类似, 寻思着如何获得所有的因式. 这个是后面的话了, 先来解决一下这道题:
. 代码分块:
第一步: 套用素数识别公式:
- bool judge(int x){
- for(int i=2;i<sqrt(x);i++)
- if(x%i==0)
- return false;
- return true;
- }
先判断输入的数是否是素数, 进行一下特判, 因为是素数的话就直接输出 1 和本身的数就好了~
第二步: 核心模块:
- for(int i = 2;i<=sqrt(temp);i++)
- {
- temp_num = 1;
- for(int j = i;j*temp_num<=temp;j++)
- {
- temp_num*=j;
- if(temp % temp_num == 0 && j-i+1> ans)
- {
- ans = j-i+1;
- temp_count = i;
- }
- }
- }
外层 for 来启动 start 数, 就是从哪开始整除, temp_num 实际上就是第二层 for 连续积, 同时第二层的 for 在连续积在输入的数范围内, 然后不断判断输入的数能否整除 temp_num, 而 j-i+1 实际上就是获取到连乘数的长度.
第三步: 输出
- for(int i = 0;i<ans;i++)
- {
- printf("%d",temp_count+i);
- if(i!=ans-1) printf("*");
- else printf("\n");
- }
. AC 代码:
- #include<stdio.h>
- #include<math.h>
- unsigned long long int temp;
- int temp_num,temp_count,ans;
- bool judge(int x){
- for(int i=2;i<sqrt(x);i++)
- if(x%i==0)
- return false;
- return true;
- }
- int main()
- {
- ans = 0;
- temp_count = 0;
- scanf("%d",&temp);
- if(judge(temp)){
- printf("1\n%d",temp);
- return 0;
- }
- for(int i = 2;i<=sqrt(temp);i++)
- {
- temp_num = 1;
- for(int j = i;j*temp_num<=temp;j++)
- {
- temp_num*=j;
- if(temp % temp_num == 0 && j-i+1> ans)
- {
- ans = j-i+1;
- temp_count = i;
- }
- }
- }
- printf("%d\n",ans);
- for(int i = 0;i<ans;i++)
- {
- printf("%d",temp_count+i);
- if(i!=ans-1) printf("*");
- else printf("\n");
- }
- return 0;
- }
. 解后反思:
刚刚提到一个问题就是说, 如何列出一个数的所有因式, 这里引出另外一道题:
输入一个数, 输出其所有的可能的因式分解方式:(可重复)
本质: 使用 DFS 深搜得到 AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- int n,ans=0,j=0,a[1000000]={0},temp;
- int su(int x)// 判断素数
- {
- if(x==1||x==2)return 1;
- for(int i=2;i<=sqrt(x);i++)
- if(x%i==0)return 0;
- return 1;
- }
- void dfs(int x)
- {
- if(x==n)
- {
- cout<<"="<<n<<"\n";
- temp = 0;
- ans++;
- return;
- }
- else if(x>n)return;
- else
- {
- for(int i=0;i<j;i++)
- {
- if(x*a[i]>n)break;
- if(n%(x*a[i])==0)
- {
- if(temp != 0) cout<<"*";
- if(temp == 0) if(x!=1) cout<<x<<"*",temp = 1;
- if(temp != 0) cout<<a[i];
- dfs(x*a[i]);
- }
- }
- }
- }
- int main()
- {
- while(cin>>n)
- {
- if(su(n));
- else
- {
- for(int i=2;i<=n/2;i++)
- {
- if(n%i==0)
- a[j++]=i;
- }
- temp = 0;
- dfs(1);
- }
- cout<<n<<"* 1 ="<<n<<endl;
- }
- return 0;
- }
使用示范:
注解: 这种深搜 DFS 方式值得品味思考, 能够给今后的因式分解找到最优解有极大帮助, 希望能分享给有用的人.
注: 如果有更好的解法, 真心希望您能够评论留言贴上您的代码呢~ 互相帮助互相鼓励才能成长鸭~~
来源: http://www.bubuko.com/infodetail-2977324.html