输出自然数n的所有因子

假设 n = i * j(i <= j) ， k = j – i >= 0

思路一：

j = n / i>=i(注意：i – int(n / i) 随着i的增大而增大，int(n/i)指n/i的整数部份)

从i = 1 开始判断 i是否能被n整除，当int(n / i) < i时终止

思路二：

n = i * (i + k)=>k = (n – i * i) / i>= 0=>k = m / i >= 0 （设m = n – i * i）

从i = 1 开始判断 i是否能被m整除，当m < 0（即k < 0）时终止

思路三：

假设 n =A^a * B^b … Z^z其中AB…Z为n的质因子

假设 na = n / A^a，可以将 na 与0到a个A进行组合，得到a+1个因子，

对每个组合中的na，可以采用类似的方法，得到其它因子。

最终可得到 (a+1)*(b+1) … *(z+1)个因子

//第一种实现方法 可能存在大量重复计算

void output(unsigned k) { printf("%un",k); }

 

static void factor_odd(unsigned n,unsigned k = 1,unsigned beg = 3)

{

 assert(n & 1);

 assert(beg & 1);

 if (n == 1) return output(k);

 assert(n >= beg);

 

 for (unsigned i = beg,count = 0; ;i += 2) {

    //if (n % i) {

    // if (i <= n / i) continue; 

    // output(k);    //n是质数

    // output(k * n);

    // return;

    //}

    if (i > n / i) {

      output(k);    //n是质数

      output(k * n);

      return;      

    }

    if (n % i) continue;

   

    ++count;

    n /= i;

    while (n % i == 0) { ++count; n /= i; }

    for (unsigned j = 0,kk = k; j <= count; ++j,kk *= i) 

      factor_odd(n,kk,i + 2);

    return;  

 }

}

 

void factor(unsigned n)

{

 unsigned count = 0;

 while (n % 2u == 0) { ++count; n /= 2u;}

 for (unsigned j = 0,k = 1; j <= count; ++j,k *= 2) factor_odd(n,k,3);

 printf("---n"); 

}

//第二种实现方法 多费点内存

void factor_bfs(unsigned n)

{

 const unsigned KK = 64; //64位整数的质因子个数肯定小于64

 unsigned va[KK],vb[KK],sz = 0; //va、vb分别记录质因子及其数目

 unsigned count = 0;

 while (n % 2u == 0) { ++count; n /= 2u;}

 if (count) { va[sz] = 2; vb[sz++] = count; };

 for (unsigned i = 3; ; i += 2) {

    if (i > n / i) {

      if (n != 1) { va[sz] = n; vb[sz++] = 1; }

      break;

    }

    if (n % i == 0) {

      unsigned count = 0;

      do { n /= i; ++count; } while (n % i == 0);

      va[sz] = i;

      vb[sz++] = count;

    }

 }

 if (sz == 0) return;

 

 std::deque<unsigned> dq;

 for (unsigned j = 0,s = 1; j <= vb[0]; ++j,s *= va[0]) dq.push_back(s);

 for (unsigned i = 1; i < sz; ++i)

    for (unsigned s = va[i],dsz = dq.size(),j = 0; j < vb[i]; ++j,s *= va[i])

      for (unsigned k = 0; k < dsz; ++k) { dq.push_back(dq[k] * s); }

 std::copy(dq.begin(),dq.end(),std::ostream_iterator<unsigned>(std::cout,"n"));

}

原文出处： http://www.cnblogs.com/flyinghearts/archive/2011/03/22/1992002.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!