输出自然数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 

假设 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("%u\n",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

总结

以上是内存溢出为你收集整理的输出自然数n的所有因子全部内容，希望文章能够帮你解决输出自然数n的所有因子所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。