2

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

4

3 回答 3

3

如果你知道质因数，就很容易找到一个数的除数；只取所有因素的多重性的所有可能组合。

对于小到 10^12 的n，试除法应该是一种足够快的因式分解方法，因为您只需检查高达 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 也无法除n，但是 24505 % 5 = 0，所以 5是 24505 的因数，n减少到 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之一必须小于n的平方根（除了p和q相等且n是完美平方的情况），并且因为我们已经完成了试除法由所有p和q小于 29 的平方根，它必须是素数，因此是最终因子。所以我们看到 24505 = 5 * 13 * 13 * 29。

我在我的文章 Programming with Prime Numbers中讨论了这些算法。

于 2012-10-30T19:31:33.683 回答
2

下面是一个示例程序，它计算 n 的大于 m 的除数的数量。如果有 c 个除数，则 largeDivs() 代码在 O(c) 时间内运行。largeDivs() 也以 n 表示为因式数，其中 nset 是形式对 (p_i, k_i) 的列表，使得 n = Product{p_i**k_i for i in 1..h}。一些示例输出显示在程序之后。check() 例程用于证明 largeDivs() 产生正确的结果。对于较小的 m 值， check() 需要很长时间。

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
于 2012-10-30T23:32:10.203 回答
0

这取决于应用程序，但如果性能是这样一个问题，我会使用预先生成的哈希表。显然，将 10^12 个条目存储在内存中可能是不切实际的（或至少是不可取的），所以我会进行第 k 个素数的除法测试，只为不能被前k个素数整除的数字生成哈希表条目。

例如，虽然写得很粗糙且未经测试，但这应该给你一个想法：

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];
于 2012-10-30T19:54:24.383 回答