分解质因数：整除问题

2019-11-06 07:01:57

字体：大中小

来源：转载

供稿：网友

分解质因数：整除问题

问题来源：题目1104：整除问题

解题思路：

在c语言中，1000！太大，不能直接计算，一般的处理也不行。

原理：如果b能整除a，那么a的每个质因子的次数都要大于b对应质因子的次数

一种可行的方法是：

将1、2、…n分别进行素数分解，得出每个素数用到的次数记录到数组an[]中然后对a进行素数分解，同样记录下各个素数用到的次数到数组bn[]中遍历an与bn，对bn[i]不为零，若an[i]为零，则k=0若an[i]不为零，则min{an[i]/bn[i]}即为k，若bn[i]==0，则不用考虑。

#include <iostream>#define MAX 1005#define INF 10000005using namespace std;int sushu(int x);int a[MAX];int an[MAX];int bn[MAX];int a_number = -1;int main(){ for(int i=2; i<1000; i++) //找出0～1000中有哪些素数，记录在数组a中 if(sushu(i)) a[++a_number] = i; int n,s; while(cin >> n >> s) { int flag = 0; for(int i=0; i<1000; i++) //数组an和bn清零 { an[i] = 0; bn[i] = 0; } for(int i=1; i<=n; i++) //an[i]记录n!中素数为a[i]的个数 { int temp = i; for(int j = a_number; j>=0; j--) //对于temp，分解质因数，没分解一个对an[i]更新 { if(!(temp%a[j])) { temp /= a[j]; an[j++]++; //j＋＋是因为一个数分解质因数的时候，一个质因数的个数可能不止一个，比如9有两个质因数3。所以temp为a［j］的质因数也可能不止一个，所以要多次测试，不然for中的j－－，使得只是测试一次a［j］。 } if(temp<2) break; } } int temp = s; for(int j = a_number; j>=0; j--) //对于s分解质因数，分解后对bn跟新，bn用于保存s的各个质因数的个数 { if(!(temp%a[j])) { temp /= a[j]; bn[j++]++; } if(temp<2) break; } for(int i=0;i<=a_number;i++) if(bn[i]) { if(!an[i]) //如果bn[i]!=0,而an[i]＝＝0，则说明不能整除，k＝0 { flag = 1; break; } an[i] = an[i]/bn[i]; //如果bn[i]和an[i]都不为零；遍历i中min{an[i]/bn[i]}即为k，记录在响应的an［i］中 } else an[i] = INF; //当bn[i]==0,说明an[i]/bn[i]＝无穷大 if(flag) { cout << 0<< endl; continue; } int minn = INF; //找出min{an[i]/bn[i]}即为k for(int i=0;i<=a_number;i++) if(minn>an[i]) minn = an[i]; cout<<minn<<endl; } return 0;}int sushu(int x) //判断x是否为素数{ for(int i=2; i<x; i++) if(!(x%i)) return 0; return 1;}

上一篇：Unity3D学习：第二周作业

下一篇：静态链表

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注