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

数学吧关注：889,510贴子：8,752,132

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

送TA礼物

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

一般说上界都是和n大小直接相关的，但n的约数个数和大小没什么关系，只和它质因数分解的结果有关。这样还讨论上界有意义么？

2楼2010-11-06 00:19

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

3楼2010-11-06 00:27

本来就没有数学意义啊，如果你是指编程的意义的话好办啊：求一个约数开一个空间就不会浪费了。
求约数个数等价于质因数分解，所以是NP问题。与其去探究这个，倒不如直接探究质因数分解...

4楼2010-11-06 00:40

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

5楼2010-11-06 01:07

顶起来

IP属地:广东

6楼2010-11-06 11:27

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

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴