計數一個整數的除數而不只是枚舉它們（或估計是否不可能）？

是否可以計算一個整數具有的除數，而不必檢查每個除數達到sqrt(n)？如果沒有，至少有一種方式估計或近似有多少除數？計數一個整數的除數而不只是枚舉它們（或估計是否不可能）？

例如，28有六個因子（1,2,4,7,14,28）。 15有四個（1，3，5，15）。我想要說明的是，有多少除數242134575355654335549798955848371716626563756785沒有計算所有的方法（或者至少猜測並從那裏取得）。

來源

2015-11-15 JesseTG

你還可以加入一些例子嗎？ –

[Integer因式分解算法]（https://en.wikipedia.org/wiki/Category:Integer_factorization_algorithms） –

我投票結束這個問題，因爲它不是關於編程，而是關於數學。 –

如果一個數的質因數分解是已知的

N = p1^e1 * p2^e2 * ... * pn^en

除數的數目是(e1+1)*(e2+1)* ... *(en+1)

例如242134575355654335549798955848371716626563756785 = 5 * 48426915071130867109959791169674343325312751357具有4個除數

頭號更高242134575355654335549798955848371716626563756786 = 2 * 101203 * 757790982862309619 * 1578643235504300177689649有16個因子。

有一些算法可以找到數字的主要因式分解，比試驗分區快得多，達到sqrt(n)。對於大數字，它仍然需要一段時間...

來源

2015-11-15 07:22:47 Henry

但是，再一次，如何讓第一手的素因子分解呢？ –

如果有很多小的因素，素數因子分解將會很快。（你找到的每個除數都減少了問題的大小）。只有數字纔是最重要的，或者是大素數的產物，需要花費很多時間。你的答案意味着沒有找到它們而沒有計算除數的任何技巧。你確定沒有已知的算法嗎？如果是這樣，你知道是否證明沒有一個？我的意思是，我不認爲有一個，但我根本不是一個數字理論家，有很多我不知道的東西。：P –

@PeterCordes當然，人們永遠無法確定沒有任何竅門，而且我也不知道沒有證據證明不存在。 – Henry

-1

有一種方法可以比sqrt（N）更快地分解數字，但是如果條件爲真，則使用Eratosthenes篩選。 Here是我學到的一個很好的解釋。你可以問我澄清。

來源

2015-11-15 08:39:15

實際上並非如此，有些方法可以更快地分解。 – harold

你說有辦法比logN更快或者比sqrt（n）更快，並且n <= 10^7條件不成立？ –

比sqrt（N）更快，n <= 10^7條件沒有什麼意義，這會迫使即使是最糟糕的算法變成常量時間。 – harold

計數一個整數的除數而不只是枚舉它們（或估計是否不可能）？

回答

相關問題