|
以现有的研究结果来看,在计算机上做因数分解和手算其实是一样的
例如对50进行分解,我们知道2, 3, 5, 7, 11, 13....是质数
先用最小的试除,50 = 2 * 25,把2记下来,然后对25尽行分解
直到最后出现一个质数
质数表的建法在上两个挑战中已经练习过了,那么剩下的问题就是,需要多大的质数表呢?
这时候需要考虑的是最坏情况,假设987654321是个质数,那么需要多少个小质数来试除才能判断出来?
这又转化到了一个熟悉的问题,判断质数试除到√n就够了,如果a * b = n 且 b > √n,那么必然有a < √n,a前面已经验证过了。
#include <stdio.h>
#include <math.h>
char buf[31427+1];
int prime_table[5000];
int main()
{
int i, j;
int pos = 0;
int upper = sqrt(31427);
int max_pdiv = -1;
int n = 987654321;
buf[0] = buf[1] = 0;
for(int i=2; i<=upper; ++i){
while(buf[i] == 1)
i++;
prime_table[pos++] = i;
buf[i] = 1;
for(j = i*i; j<31427+1; j+=i)
buf[j] = 1;
}
for(i = 3; i < 31427+1; ++i)
if(buf[i] == 0)
prime_table[pos++] = i;
while(1){
int found = 0;
int upper = sqrt(n);
for(i=0; i<pos && prime_table[i] <= upper; ++i)
if(n % prime_table[i] == 0){
found = 1;
n /= prime_table[i];
max_pdiv = prime_table[i];
}
if(!found){
if(n > max_pdiv)
max_pdiv = n;
break;
}
}
printf("%d\n", max_pdiv);
return 0;
}
为什么max_pdiv初始值是-1?这时候还不知道第一个遇到的质因数是多少,但是可以肯定它比-1大,所以prime_table[i] > max_pdiv在第一次试除成功是一定可以满足的
另外还要注意一点,试除到最后可能剩下一个质数,所以要判断下n是不是大于max_pdiv
|
|