质因子 百科内容来自于: 百度百科

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

性质

两个没有共同质因子正整数称为互质
数字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 = 2x 2,8 = 2x 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\n",now,x);//debug
}
// printf("now: %d last: %d\n",now,last);//debug
last = now;
}
}
return last - t;
// printf("answer is %d\n",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\n",i,dp[i]);
if (i%1000 == 0) cout<<i<<endl;//debug
}
}
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定