分解质因数

以下两行表示 n＝p1a1p2a2…pkak，其中 p1、p2…pk 是 n 的质因数。

int n; int p[N], a[N], k;

(1) 分解质因数

file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps21.png方法一：产生一个从2到n的质数表，然后从2开始除。在除干净之后换下一个因数。

方法二：不产生质数表，直接从2开始除。在除干净之后换下一个因数。（注：n 是素数时速度会非常慢。）

int i=2; top=-1; while (n>1) { if (n%i==0) {   p[++k]=i;   a[k]=0;

第十二单元 数论算法

  while (n%i==0) n/=i, a[k]++;

}

else   i++;     // 换下一个因数（提示：如果上面的n%i==0为真，那么i肯定是质数）

}

分解质因数的实际应用是使用因数表优化乘除法。

(2) 除数函数设 d(n)为 n 的所有因数的个数，由乘法原理可知，

d(n)＝(a1+1)(a2+1)…(ak+1)。

(3) 欧拉函数

设φ(n)为1,2,3,…n 中与 n 互素的元素个数，那么φ(n)可以用容斥原理计算。但是容斥原理比较复杂，计算速度也非常慢。所以要用另一种形式求解：

φ(n)＝n(1－1)(1－1)…(1－1)＝n·p1－1·p2－1·…·pk－1) p1        p2        pk        p1        p2        pk

可以直接计算：

int phi(int n) {  int m = (int)sqrt(n);  int ans=n; // 这里是边分解质因数边计算。如果已经分解质因数，就可以直接计算了。  for (int i=2;i<=m;i++)   if (n%i==0)   {    ans=ans / i * (i-1);    while (n%i==0) n/=i;   } if (n>1) ans=ans / n * (n-1);   // 防质数  return ans; }

如果要产生欧拉函数表，可以用递推的方法完成：

void phi_table(int *a, int n)

{  memset(a,0,sizeof(int)*(n+1));  a[1]=1;

  

for (int i=2; i<=n; i++)   if (!a)    for (int j=1; j<=n; j+=i)

   {

    if (!a[j]) a[j]=j;     a[j]=a[j]/i*(i-1)

   }

}