1

範囲が[1、2 Million]の場合、この範囲の数値ごとに、各整数の除数の数を生成して配列に格納する必要があります。

したがって、x = p1 ^（a1）* p2 ^ a2 * p3 ^ a3の場合、p1、p2、p3は素数であり、xの約数の総数は（p1 + 1）（p2 + 1）（p3 + 1）。2000未満のすべての素数を生成し、範囲内の整数ごとに、試行除算を行って各素因数の累乗を取得し、上記の式を使用して除数の数を計算し、配列に格納しました。ただし、これを行うには非常に時間がかかり、指定された範囲内のすべての数値の除算器の数を生成するのに約5秒かかります。

この合計を他の効率的な方法で行うことはできますか？各数値を因数分解せずに行うことができますか？

以下は私が現在使用しているコードです。

typedef unsigned long long ull;
void countDivisors(){
    ull PF_idx=0, PF=0, ans=1, N=0, power;
    for(ull i=2; i<MAX; ++i){
        if (i<SIEVE_SIZE and isPrime[i]) factors[i]=2;
        else{
        PF_idx=0;
        PF=primes[PF_idx];
        ans=1;
        N=i;
        while(N!=1 and (PF*PF<=N)){
            power = 0;
            while(N%PF==0){ N/=PF; ++power;}
            ans*=(power+1);
            PF = primes[++PF_idx];
        }
        if (N!=1) ans*=2;
        factors[i] = ans;
        }
    }
}
4

1 に答える 1

3

まず、式が間違っています。あなたの公式によると、12 の約数の合計は 12 になるはずです。実際には 28 です。正しい公式はです。(p1a1 - 1)*(p2a2 - 1) * ... * (pkak - 1)/( (p1 - 1) * (p2 - 1) * ... * (pk - 1) )

とはいえ、最も簡単な方法はおそらくふるいにかけることです。オフセットをうまく使うこともできますが、簡単にするために、0 から 200 万までの 2,000,001 個の整数の配列を作成するだけです。0 に初期化します。それで：

for (ull i = 1; i < MAX; ++i) {
    for (ull j = i; j < MAX; j += i) {
        factors[j] += i;
    }
}

これは非効率に感じるかもしれませんが、それほど悪くはありません。までの数にかかる総作業量NはN + N/2 + N/3 + ... + N/N = O(N log(N))、試行分割よりも桁違いに小さくなります。また、演算はすべて加算と比較であり、整数の場合は高速です。

元のアイデアと数式を続行したい場合は、エラトステネスの修正ふるいを使用して、各数値の素因数をリストする 100 万から 200 万までの配列を作成することで、効率を高めることができます。その配列の構築はかなり高速であり、任意の数を取り、因数分解することができます。試行分割よりもはるかに高速です。

于 2012-02-07T07:01:55.023 に答える