wordpress mv网站模板,餐饮最有效的营销方案,做软件的叫什么职业,医院网站建设的规划方案一、数n的质因子分解
题目描述#xff1a;
输入一个数n#xff08;n10^6#xff09;,将数n分解质因数#xff0c;并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入 5
输出 5 1
输入 10
输出 2 1 5 1
朴素解法#xff1a;
首先求出1~n的所有质数…一、数n的质因子分解
题目描述
输入一个数nn10^6,将数n分解质因数并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入 5
输出 5 1
输入 10
输出 2 1 5 1
朴素解法
首先求出1~n的所有质数每个质数每个质数的进行去除要保证n中除尽除完直到把n除到1为止。
程序实现
#includebits/stdc.husing namespace std;const int N1e6;int prime[N],idx;
bool st[N];void init(){for(int i2;iN;i){if(!st[i]) prime[idx]i;for(int j1;prime[j]*iN;j){st[prime[j]*i]1;if(i%prime[j]0) break;}}
}
int main(){init();int n;cinn;if(!st[n]) coutn 1endl;else{for(int i1;prime[i]niidx;i){int pprime[i];int sum0;while(n%p0){sum;n/p;}if(sum) coutp sumendl;}}return 0;
}
优化思路
其一n如果除掉了前面的某个质因子后面不能再被某个质因子的倍数整除了证明比较简单使用反证法就可以。
其二n中最多只含有一个大于的因子。证明通过反证法如果有两个大于sqrt(n)的因子那么相乘会大于n矛盾。证毕
基于上面的两条结论只要从1~把每个数都除一遍除尽除完最后剩下的数如果不为1这个数就是最大的质因子
代码实现
#includebits/stdc.h
using namespace std;int main(){int n;cinn;for(int i2;in/i;i){int sum0;while(n%i0){sum;n/i;}if(sum) couti sumendl;}if(n!1) coutn 1endl;return 0;
}
二、阶乘的质因子分解
题目描述
题目分析
我们枚举1∼n的所有数把每一个数的质因子加到一个数组里。 最后输出质因子数量大于0的数。 时间复杂度为O(n^2/ln n) 程序实现
#includebits/stdc.h
using namespace std;
const int N1e6;
int prime[N],idx;
bool st[N];void init(){for(int i2;iN;i){if(!st[i]) prime[idx]i;for(int j1;prime[j]*iN;j){st[prime[j]*i]1;if(i%prime[j]0) break;}}
}
int ans[N]; //ans[i]表示第i个质因子的个数
int main(){init();int n;cinn;for(int i2;in;i){ //枚举每一个数for(int j1;prime[j]ijidx;j){int pprime[j];int curi;while(cur%p0){ans[j];cur/p;}}}for(int i1;iidx;i){if(ans[i]) coutprime[i] ans[i]endl;}return 0;
}
优化思路
我们不去枚举每个数而是枚举每个质因子看下在2~n中每个质因子出现的次数
在1x2x3x4x5x6x......x n-1 x n其中
能够被2整除的数有
1*2 2*2 3*2....... i*2 其中2*in 个数 in/2
能够被整除的数有:
1* 2* 3*......i* 其中i*n 个数in/
...........
在统计被2整除的个数时相当于把每个数都除了2剩下的数还有可能被2整除那些数是的数的数有n/个剩下的数还有可能被2整除那些数是的数的数有n/个............所以2作为因子的个数为 其中
同理3作为因子的个数为 其中
等等
所以只要枚举每个质数使用循环在求出该质数作为因子的个数即可每个质数求解时
p,质数的个数为因此总的时间复杂度为** 即时间复杂度为O(n)
