定义

性质

相关的定理

求质因子和的算法

定义

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

性质

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

数字1与任何正整数（包括1 本身）都是互质。

This is because it has no prime factors; it is the empty product。

正整数的因数分解给出一连串的质因子；所有质因子相乘后。质因子如重复会以指数表示。

根据Fundamental theorem of arithmetic，任正整数有独一无二的质因子分解式。

设任正整数n，其质因子数目及其质因子的和是n的算术函数(arithmetic function)。

例子 6的质因子是3和2。(6 = 3 × 2) 5只有1个质因子，5本身。（5是质数。）

100有2个质因子：2和5。(100 = 2 x 50, 且100=5 x 20，只有2和5是质数)

2、4、8、16等只有1个质因子：2（2是质数，4 = 2 x 2，8 = 2 x 4，如此类推。偶数(6除外)的因子中，只有2是质数。）

1没有质因子。（1是empty product）

相关的定理

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

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

求质因子和的算法

求因子和的方法：

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

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

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

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

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

36:

0: 1

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

2: 3 6 12 , 9 18 36 sum = 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

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

主要的函数：

cal (x) 求 x 的因子和

int cal(int a) //计算 a 的因子和

{

int i;

int last,now;// sum

last = 1;now = 0;

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

int t = a;

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

{

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

{

x = last;

now = last;

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

{

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

a /= primes[i];

x *= primes[ i ];

now += x;

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

}

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

last = now;

}

}

return last - t;

// printf("answer is %d\",last);

}

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

void work2()

{

int i,j;

dp[ 1 ] = 1;

int temp;

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

{

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

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

break;

int i2 = i;

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

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

{

temp = temp* primes[ j ] + 1;

i2 /= primes[ j ];

}

int last = dp [ i2 ];

dp [ i ] = temp* last;

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

if (i%1000 == 0) cout<<i<<endl;//debug

}

}