挑战7

rosynirvana

以现有的研究结果来看，在计算机上做因数分解和手算其实是一样的
例如对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