4

我需要计算数字 N 的除数总数（而不关心除数的值是什么），并在所有此类数字 N 的 40-80 次操作内进行计算。我该怎么做？这不是一个家庭作业问题。我尝试了Pollard 的 Rho算法，但结果对我的目的来说太慢了。这是我在python中的代码。如果可能的话，我怎样才能提高它的性能？

def is_prime(n):    
    if n < 2:
        return False
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,
         43,47,53,59,61,67,71,73,79,83,89,97]
    def is_spsp(n, a):
        d, s = n-1, 0
        while d%2 == 0:
            d /= 2; s += 1
        t = pow(int(a),int(d),int(n))
        if t == 1:
            return True
        while s > 0:
            if t == n-1:
                return True
            t = (t*t) % n
            s -= 1
        return False
    if n in ps: return True
    for p in ps:
        if not is_spsp(n,p):
            return False
    return True

def gcd(a,b):
        while b: a, b = b, a%b
        return abs(a)

def rho_factors(n, limit=100):
    def gcd(a,b):
        while b: a, b = b, a%b
        return abs(a)
    def rho_factor(n, c, limit):
        f = lambda x:    (x*x+c) % n
        t, h, d = 2, 2, 1
        while d == 1:
            if limit == 0:
                raise OverflowError('limit exceeded')
            t = f(t); h = f(f(h)); d = gcd(t-h, n)
        if d == n:
            return rho_factor(n, c+1, limit)
        if is_prime(d):
            return d
        return rho_factor(d, c+1, limit)
    if -1 <= n <= 1: return [n]
    if n < -1: return [-1] + rho_factors(-n, limit)
    fs = []
    while n % 2 == 0:
        n = n // 2; fs = fs + [2]
    if n == 1: return fs
    while not is_prime(n):
        f = rho_factor(n, 1, limit)
        n = int(n / f)
        fs = fs + [f]
    return sorted(fs + [n])

def divs(n):
    if(n==1):
        return 1
    ndiv=1
    f=rho_factors(n)
    l=len(f)
    #print(f)
    c=1
    for x in range(1,l):
        #print(f[x])
        if(f[x]==f[x-1]):
            c=c+1
        else:
            ndiv=ndiv*(c+1)
            c=1
       # print ("C",c,"ndiv",ndiv)
    ndiv=ndiv*(c+1)
    return ndiv
4

3 回答 3

2

首先，你的意思是找到除数的总数，分解中的素数，还是不同的素数除数？例如，12 = 2 * 2 * 3 有 6 个除数 (1,2,3,4,6,12)，分解中的 3 个素数 (2,2,3)，以及 2 个不同的素数除数 (2,3) . 您想要 6、3 还是 2 作为结果？我将假设您在剩下的时间里想要其中的第二个，但如果您对其他一个感兴趣，我认为不会有任何实质性的变化......

其次，你将不得不充分考虑你的数字。没有已知的捷径可以在不找到因子本身的情况下找到素因子的数量。（值得注意的例外是，您可以快速测试因子数是 ==1 还是 >=2。）

10^12 没那么大。您只需要测试除数到该数字的平方根，最多为 10^6。假设在 2GHz 的现代 CPU 上除法需要 20 个周期，测试一百万个除数只需 10 毫秒。

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  long long n = atoll(argv[1]);
  for (int i = 2; i < 1000000; i++) {
    while (n % i == 0) { printf("%d\n", i); n /= i; }
  }
  if (n > 1) printf("%lld\n", n);
}

在我的机器上需要 23 毫秒。想知道那另外的 13 毫秒去哪儿了？

Python 大约慢了 10 倍，因为这段代码在我的机器上仍然只需要 0.23 秒：

import sys
n = int(sys.argv[1])
for i in xrange(2, 1000000):
  while n%i==0: print i; n/=i
if n>1: print n

你想要多快？

于 2012-09-07T17:28:03.130 回答
2

我记得以前在 SPOJ 上解决过这个问题，但我不记得我使用的确切方法（如果您提供问题 ID，那就太好了）。您是否尝试过这里的幼稚方法？它的复杂度为O(sqrt n)，大约O(10 ^ 6)在最坏的情况下。模运算符可能有点慢，但值得一试。以下是在 C++ 中完成时的外观：

int cntdiv = 0;
for(int i = 2; i * i <= x; i ++) {
    if(x % i == 0) {
        cntdiv += 1 + (i * i != x);
    }
}
//cntdiv is now your count
于 2012-09-06T19:11:16.420 回答
-1

我记得有一个基于数字和其他特征的数字总和的解决方案
例如，3411可以被9整除，因为3 + 4 + 1 + 1 = 9，数字总和可以被9整除，而不是一个数字也能被 9 整除。与其他数规则类似。

于 2012-09-06T20:07:28.713 回答