输出自然数n的所有因子

输出自然数n的所有因子,第1张

概述假设 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的所有因子所遇到的程序开发问题。

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1291261.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存