质因子（数学术语）

质因子（数学术语）

质因子 （数学术语） 次浏览 | 2022.10.28 15:40:15 更新 来源 ：互联网 精选百科 本文由作者推荐 质因子数学术语

质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。只有一个质因子的正整数为质数。

中文名

质因子

外文名

prime factor

定义

正整数的一个质数因子

所属学科

数学

性质

两个没有共同质因子的正整数互质

相关定理

质因子分解式

定义

在数论里，某一正整数的质因子指能整除该数的质数整数。

相关定理

任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=(P_1^a1)*(P_2^a2)......(P_n^an),这里P_1

这样的分解称为N的标准分解式。

求和算法

求因子和的方法：

sqrt(n)太慢，可以用一下DP的思想，

把质因子分析出来ai^x，

那么再乘一个ai+1，因子和就增加了原来的ai+1倍

如果这个质因子是2次幂，那么还得增加原来那一层的(ai+1)^2倍

速度因该是质因子的指数的和，但是受到求质因子速度的制约

36:

0:1

1:24=(1*2,1*2^2)sum=1+(2)+(4);//2*2

2:3612,91836sum=1+2+4+(3+6+12)+(9+18+26)

也就是说，如果我们知道了一层的sum，那么就可以推出下一层的sum

知道了一个数的因子和，就可以推知他的质数倍^x的那个数的因子的和，

DP来解决这道题，对于数x，把它除尽一个质数，那么x/a^k=y

那么y就是上一层的那个sum

而对于x，存在x=(1+a+a^2+a^3..a^k)*y

上面这个方法要100s,题目要求不是求因子和，所以如果有质数在[a,b]内，那么最大的质数就是answer

主要的函数：

cal(x)求x的因子和

intcal(inta)//计算a的因子和

{

inti;

intlast,now;//sum

last=1;now=0;

intx;//因子的^x与前一阶段

intt=a;

for(i=0;primes[i]<=a;i++)

{

if(a%primes[i]==0)

{

x=last;

now=last;

while(a%primes[i]==0)

{

//printf("%dcandiv%d:",a,primes[i]);//debug

a/=primes[i];

x*=primes[i];

now+=x;

//printf("now:%dx:%d ",now,x);//debug

}

//printf("now:%dlast:%d ",now,last);//debug

last=now;

}

}

returnlast-t;

//printf("answeris%d ",last);

}

第二个DP虽然TLE，但是感觉有思考价值，求很多数的因子和时，也许能用的到

voidwork2()

{

inti,j;

dp[1]=1;

inttemp;

for(i=2;i<=1000000;i++)

{

for(j=0;primes[j]<=i;j++)//寻找上一层

if(i%primes[j]==0)

break;

inti2=i;

temp=1;//求前面那个系数

while(i2%primes[j]==0)

{

temp=temp*primes[j]+1;

i2/=primes[j];

}

intlast=dp[i2];

dp[i]=temp*last;

//printf("dp[%d]=%d ",i,dp[i]);

if(i%1000==0)cout<

}

}

相关拓展

子模块电容电压均衡控制策略是保证模块化多电平换流器（modularmultilevelconverter,MMC）正常运行的重要环节。对于每相桥臂含有大规模数量子模块的模块化多电平换流器高压直流输电（modularmultilevelconverterbadhighvoltagedirectcurrent,MMC-HVDC）系统,减小排序复杂度对MMC-HVDC工程控制器设计难度以及硬件需求的降低具有重要意义。

该文基于质因子分解法提出一种优化的混合排序法,通过引入希尔排序算法大幅度降低排序次数,从而降低仿真时间,降低了对系统硬件的要求。推导适用于MMC-HVDC系统的希尔排序步长的时间复杂度,给出基于混合排序法的排序次数计算公式,分析分组层数对系统降低频率的影响,得到分组层数与混合排序法优化效率成反比例关系的结论。最后在PSCAD/EMTDC中搭建两端401电平MMC-HVDC模型进行仿真,仿真结果验证了混合排序法及分组层数对优化效率影响的分析的有效性与正确性。[1]

参考资料