n的约数个数上界【数学吧】

数学吧关注：933,548贴子：8,938,247

先声明不是问怎么求n的约数个数。。
很容易证明n的约数个数不超过2√n（小于等于√n的和大于等于的一一对应）
但是实际操作中发现这个个数在n较大时是远小于2√n的
有没有阶数更小的上界

送TA礼物

1楼2010-11-05 23:57回复

有意义。至少我可以开更小的空间保存这些约数了。
貌似找这个个数是一个NP问题，那么在证明P=NP之前这些小优化很重要……

3楼2010-11-06 00:27

不感兴趣

开通SVIP免广告

回复4楼：
从质因数的角度入手给上界也行。不要说没意义，同样是NP问题，从O(n!)到O(2^n)都是很大的飞跃啊。反正我需要一个阶数更小的上界，不一定证明最小，比根号那个小就行了

5楼2010-11-06 01:07

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴