質因子（數學術語）

質因子（數學術語）

質因子 （數學術語） 次瀏覽 | 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]

參考資料