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 が必要ですか? これ以降は 2 番目のものが必要になると思いますが、他の 1 つに興味があったとしても、実質的には何も変わらないと思います...

次に、数を完全に因数分解する必要があります。素因数自体を見つけることなく、素因数の数を見つけることができる既知の近道はありません。(因数の数が ==1 か >=2 かをすばやくテストできるという注目すべき例外があります。)

10^12 はそれほど大きくありません。除数をテストする必要があるのは、数値の平方根 (最大で 10^6) までだけです。2 GHz の最新の CPU で除算に 20 サイクルかかるとすると、100 万の除数をテストするのにわずか 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 ミリ秒はどこに行ったのだろうか?

私のマシンでは、このコードがまだ 0.23 秒しかかからないため、Python は約 10 倍遅くなります。

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 で割り切れます。 9 で割り切れる場合もあります。他の数のルールも同様です。

于 2012-09-06T20:07:28.713 に答える