不小于另一个数字的数字的因子数

Question

是否有任何有效的方法来查找不小于另一个数字（比如m）的数字（比如说n）的除数的数量。 n可以高达10^12。 我想过筛算法&然后找到除数的数量。 我的方法检查所有从m到n的平方根的数字。 但我认为有另一种方式（高效）来做到这一点。

Answer 1

下面是一个例子程序，计算是大于m n个约数的个数。如果有c个除数，那么largeDivs（）代码在时间O（c）中运行。 largeDivs（）也以n表示一个因式分解开始，nset是一对形式对（p_i，k_i）的列表，使得n = Product {p_i ** k_i for i in 1..h}。程序之后会显示一些输出示例。 check（）例程用于演示largeDivs（）产生正确的结果。 check（）需要很长时间才能获得较小的m值。

def largeDivs(n, nset, m): 
    p, k = nset[-1] 
    dd = 0 
    if len(nset) > 1: 
     nn, mm = n/p**k, m 
     for i in range(k+1): 
      dd += largeDivs(nn, nset[:-1], mm) 
      mm = (mm + p-1)/p 
    else: 
     c, v = k+1, 1 
     while v<m and c>0: 
      c, v = c-1, v*p 
     return c 
    return dd 

def check (n,m,s): 
    if m<1: 
     return s 
    c = 0 
    for i in range(m,n+1): 
     if (n%i)==0: 
      c += 1 
    return c 


tset = [(2,3),(3,2),(11,1),(17,1),(23,2)] 
n = s = 1 
for i in tset: 
    s *= 1+i[1] 
    n *= i[0]**i[1] 
print 'n=',n, ' s=',s 
m=0 
for i in range(8): 
    print 'm:', m, '\t', largeDivs(n, tset, m), ' Check:',check(n,m,s) 
    m = 10*m + 5 

输出示例：

n= 7122456 s= 144 
m: 0 144 Check: 144 
m: 5 140 Check: 140 
m: 55 124 Check: 124 
m: 555 95 Check: 95 
m: 5555  61 Check: 61 
m: 55555 28 Check: 28 
m: 555555 9 Check: 9 
m: 5555555 1 Check: 1 

Answer 2

如果你知道素数因素，很容易找到数字的除数;只是采取所有因素的多重性的所有可能的组合。

对于n小到10^12，试划应该是一个足够快的因子分解方法，因为你只需要检查潜在的因素高达10^6。

编辑：加入关于“所有可能的组合”的讨论以及通过审判划分的保理。

考虑数24505 = 5 * 13 * 13 * 29，要列举它的除数，采取一切因素的多重性的所有可能的组合：

5^0 * 13^0 * 29^0 = 1 
5^0 * 13^0 * 29^1 = 29 
5^0 * 13^1 * 29^0 = 13 
5^0 * 13^1 * 29^1 = 377 
5^0 * 13^2 * 29^0 = 169 
5^0 * 13^2 * 29^1 = 4901 
5^1 * 13^0 * 29^0 = 5 
5^1 * 13^0 * 29^1 = 145 
5^1 * 13^1 * 29^0 = 65 
5^1 * 13^1 * 29^1 = 1885 
5^1 * 13^2 * 29^0 = 845 
5^1 * 13^2 * 29^1 = 24505 

它也不难通过对因子的数审判分庭。这是算法，您可以将其转换为您最喜欢的语言;它足够快足够人数达到10^12：

function factors(n) 
    f = 2 
    while f * f <= n 
     if n % f == 0 
      output f 
      n = n/f 
     else 
      f = f + 1 
    output n 

让我们来看看24505.最初因式分解˚F是2，但24505％2 = 1，所以˚F增加为3。然后˚F = 3和˚F = 4也不能划分ñ，但24505％5 = 0，所以图5是24505倍，并且ñ减少到24505/5 = 4901现在˚F = 5不变，但未能分配n，同样是6,7,8,9,10,11和12，但最后4901％13 = 0，因此13是4901的因子（也是24505），并且n减少到4901/13 = 377 。此时f = 13不变，13又是一个除数，这次减少了n = 377，所以输出13的另一个因子，并且n减少到29.在这一点上13 * 13 = 169大于29，所以退出while循环，输出最终因子29;此工作，因为如果N = PQ，然后p或q必须小于的Ñ平方根之一（除非在p和q相等且Ñ的情况下是一个完美的正方形），并且由于我们已经完成了除了29的平方根以外的所有p和q的尝试划分，所以它必须是素数，并且因此是最终因子。所以我们看到，24505 = 5 * 13 * 13 * 29

我讨论这些类型的算法我essay编程与素数。

Answer 3

它取决于应用程序，但如果性能是这样的问题，我会使用预生成的哈希表。很明显，10^12个条目可能不适合（或至少不受欢迎）存储在内存中，所以我会进行分割测试，直到质数，生成散列表条目仅用于那些第一个不能被其整除的数字素数。

例如，虽然粗制滥造书面和未经考验的，这应该给你一个想法：

int number = 23456789; 
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 0}; 
int pfactors = 0; 
int* prime = primes; 
float temp; 

// check until we reach the end of the array (0) 
while (prime) 
{ 
    // divide by prime and check if result is integer 
    temp = (float)number/*prime; 
    if (temp == floor(temp)) 
    { 
     // if so, increment count of prime factors and loop (same prime again!) 
     pfactors++; 
     number = (int)temp; 
    } 
    else 
    { 
     // else try the next prime 
     prime++; 
    } 
} 

// finally, rely on hash table magic 
pfactors += pregenerated_hash[number];