唯一分解定理(c++版)
·
唯一分解定理:
任意一个正整数,都可以分成有限个素数的乘积形式
没错,这就是核心,短叭?
例如:48 = 2 * 2 * 2 * 2 * 3,54 = 2 * 3 * 3 * 3。
唯一分解定理推论:
根据分解过后的质因子种类及其个数能推出这个数有多少个因子
如:上述48 = 2 * 2 * 2 * 2 * 3 = 2^4 * 3^1
其因子数就为(4+1) * (1+1) 就是根据组合数学来推的,2的个数有0 -到 4种选法,3的个数有 0 到 1种选法
54 = 2^1 * 3^3
因子数为:(1+1) * (3+1)
代码实现把一个数分解成若干素数的乘积形式:
模板:
void weiyi(int n){
int cnt=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
p[++cnt]=i,e[cnt]=0;
while(n%i==0){
n/=i;
e[cnt]++;
}
}
}
if(n>1) p[++cnt]=n,e[cnt]=1;
}
更多推荐



所有评论(0)