谁提供一个因数分解的改进代码

来源：百度知道 编辑：UC知道 时间：2024/05/05 01:38:29
把n分解成 n=p1^a1 * p2^a2 *.... * pk^ak,
p1,p2,...,pk 是质数，n的范围是小于1000000
我已经做出了1000以内的质数表

a1,a2,...,ak存在 a[k]数组内
p1,p2,...,pk存在 p[k]数组内

谁给个代码

随手写的

#include <stdio.h>

int pn[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, /*...*/};

int main()
{
int n;
int p[8], a[8];
int len = sizeof(pn) / sizeof(int);
register int j, k;

scanf("%d", &n);
if (n == 1)
{
printf("n = 1\n");
return 0;
}
if (n < 2 || n > 1000000)
{
printf("Out of range!\n");
return 0;
}

for (j = k = 0; j < len && n > 1; j++)
{
if (n % pn[j] == 0)
{
n /= p[k] = pn[j];
for (a[k] = 1; n % p[k] == 0; n /= p[k])
a[k]++;
k++;
}
}
if (n > 1)
{
p[k] = n;
a[k] = 1;
k++;
}
printf("n = %d^%d", p[0], a[0]);