与えられた数の約数を計算するための最も最適なアルゴリズム (パフォーマンスに関して) は何でしょうか?
疑似コードまたはいくつかの例へのリンクを提供していただければ幸いです。
編集：すべての回答は非常に役に立ちました、ありがとう。私は Atkin のふるいを実装してから、Jonathan Leffler が示したものと同様のものを使用します。Justin Bozonier が投稿したリンクには、私が求めていたものに関する詳細情報が含まれています。
154821 次
26 に答える
77
Dmitriy の言うとおり、Atkin のふるいに素数リストを生成してもらいたいと思うでしょうが、それですべての問題が解決するとは思えません。素数のリストができたので、それらの素数のうちいくつが除数として機能するか (およびその頻度) を確認する必要があります。
アルゴの python を次に示し ます。ここを参照して、「件名: 数学 - 除数アルゴリズムが必要」を検索してください。ただし、リスト内のアイテムを返す代わりに、リスト内のアイテムの数を数えるだけです。
これは、数学的に何をする必要があるかを正確に説明する数学博士です。
基本的には、数値nが次の場合に要約されます
n = a^x * b^y * c^z
(ここで、a、b、および c は n の素約数であり、x、y、および z は約数が繰り返される回数です)、すべての約数の合計数は次のようになります。
(x + 1) * (y + 1) * (z + 1).
編集：ところで、a、b、cなどを見つけるには、これを正しく理解している場合、貪欲なアルゴリズムに相当することをしたいと思うでしょう。最大の素約数から始めて、さらに乗算すると数 n を超えるまで、それ自体を乗算します。次に、次に低い因数に移動し、前の素数 ^ 現在の素数を掛けた回数を掛け、次の素数が n を超えるまで素数を掛け続けます... など。約数を一緒にして、それらの数値を上記の式に適用します。
私のアルゴの説明について 100% 確信があるわけではありませんが、そうでない場合は似たようなものです。
于 2008-09-21T06:03:34.293 に答える
48
因数分解には、Atkin のふるいよりもはるかに多くの手法があります。たとえば、5893 を因数分解したいとします。その sqrt は 76.76 です... 5893 を 2 乗の積として書きます。(77*77 - 5893) = 36 は 6 の 2 乗なので、5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71 です。それがうまくいかなかったら、78*78 - 5893 が完全な正方形かどうかを調べたでしょう。等々。この手法を使用すると、個々の素数をテストするよりもはるかに速く、n の平方根に近い因子をすばやくテストできます。大きな素数を除外するこの手法とふるいを組み合わせると、ふるいのみを使用するよりもはるかに優れた因数分解法が得られます。
そして、これは開発された多数の技術の 1 つにすぎません。これはかなり単純なものです。たとえば、楕円曲線に基づく因数分解の手法を理解するのに十分な数論を学ぶには、長い時間がかかります。(私はそれらが存在することを知っています。私はそれらを理解していません。)
したがって、小さな整数を扱っていない限り、私はその問題を自分で解決しようとはしません。代わりに、非常に効率的なソリューションが既に実装されているPARIライブラリのようなものを使用する方法を見つけようとします。これで、124321342332143213122323434312213424231341 のようなランダムな 40 桁の数字を約 0.05 秒で因数分解できます。(ご参考までに、その因数分解は 29*439*1321*157907*284749*33843676813*4857795469949 です。Atkin のふるいを使用してこれを理解できなかったと確信しています...)
于 2008-09-21T08:47:26.643 に答える
35
@ヤスキー
除数関数には、完全な正方形に対して正しく機能しないというバグがあります。
試す：
int divisors(int x) {
int limit = x;
int numberOfDivisors = 0;
if (x == 1) return 1;
for (int i = 1; i < limit; ++i) {
if (x % i == 0) {
limit = x / i;
if (limit != i) {
numberOfDivisors++;
}
numberOfDivisors++;
}
}
return numberOfDivisors;
}
于 2011-03-23T14:32:23.587 に答える
30
アトキンのふるいが進むべき道であることに私は同意しません。なぜなら、分割によって数を減らすよりも、[1、n]のすべての数の素数性をチェックするのに簡単に時間がかかる可能性があるからです。
少しハックですが、一般的にはるかに高速なコードを次に示します。
import operator
# A slightly efficient superset of primes.
def PrimesPlus():
yield 2
yield 3
i = 5
while True:
yield i
if i % 6 == 1:
i += 2
i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
d = {}
primes = PrimesPlus()
for p in primes:
while n % p == 0:
n /= p
d[p] = d.setdefault(p, 0) + 1
if n == 1:
return d
def NumberOfDivisors(n):
d = GetPrimeDecomp(n)
powers_plus = map(lambda x: x+1, d.values())
return reduce(operator.mul, powers_plus, 1)
psこれはこの問題を解決するために動作するPythonコードです。
于 2008-09-23T01:53:44.487 に答える
11
この興味深い質問は見た目よりもはるかに難しく、回答されていません。質問は、2つの非常に異なる質問に分解できます。
1与えられたN、Nの素因数のリストLを見つける
2与えられたL、一意の組み合わせの数を計算します
私がこれまでに見たすべての答えは＃1を参照しており、膨大な数の場合は扱いにくいとは言えません。適度なサイズのNの場合、64ビットの数値であっても簡単です。巨大なNの場合、因数分解の問題は「永遠に」かかる可能性があります。公開鍵暗号化はこれに依存します。
質問2にはさらに議論が必要です。Lに一意の番号のみが含まれている場合は、n個のアイテムからk個のオブジェクトを選択するための組み合わせ式を使用した簡単な計算です。実際には、kを1からsizeof（L）まで変化させながら、式を適用した結果を合計する必要があります。ただし、Lには通常、複数の素数の複数のオカレンスが含まれます。たとえば、L={2,2,2,3,3,5}はN=360の因数分解です。これで、この問題は非常に困難になります。
＃2を言い換えると、コレクションCにk個のアイテムが含まれている場合、アイテムaにはa'の重複があり、アイテムbにはb'の重複があるなど、1からk-1のアイテムの一意の組み合わせはいくつありますか。たとえば、{2}、{2,2}、{2,2,2}、{2,3}、{2,2,3,3}は、L = {2,2の場合、それぞれ1回だけ発生する必要があります、2,3,3,5}。このような一意のサブコレクションはそれぞれ、サブコレクション内のアイテムを乗算することによるNの一意の除数です。
于 2008-11-04T02:52:27.333 に答える
10
あなたの質問に対する答えは、整数のサイズに大きく依存します。100 ビット未満などの小さな数の方法と、(暗号化で使用されるような) 1000 ビット以下の数の方法は完全に異なります。
于 2008-09-21T18:38:04.073 に答える
7
1行
だけあなたの質問について非常に慎重に考え、非常に効率的でパフォーマンスの高いコードを書き込もうとしました特定の数のすべての約数を画面に表示するには、1行のコードしか必要ありません! (gcc 経由のコンパイル中にオプション -std=c99 を使用)
for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number
除数を見つけるには、次の非常に高速な関数を使用できます (1 と 2 を除くすべての整数に対して正しく機能します)。
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return counter;
}
または、指定された数値を除数として扱う場合 (1 と 2 を除くすべての整数に対して正しく機能します)
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return ++counter;
}
注: 上記の 2 つの関数は、1 と 2 を除くすべての正の整数に対して正しく機能するため、2 より大きいすべての数に対して機能しますが、1 と 2 をカバーする必要がある場合は、次の関数のいずれかを使用できます (もっとゆっくり）
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
if (n==2 || n==1)
{
return counter;
}
return ++counter;
}
また
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
return ++counter;
}
小さいのは美しいです:)
于 2011-11-11T02:59:27.923 に答える
6
これを試してみてください。少しハックですが、かなり高速です。
def factors(n):
for x in xrange(2,n):
if n%x == 0:
return (x,) + factors(n/x)
return (n,1)
于 2009-07-18T03:31:27.657 に答える
6
アトキンのふるいは、指定された整数までのすべての素数を与えるエラトステネスのふるいの最適化されたバージョンです。詳細については、これをグーグルで検索できるはずです。
リストを取得したら、数値を各素数で割って、それが正確な約数 (剰余がゼロ) であるかどうかを確認するのは簡単なことです。
数値 (n) の除数を計算する基本的な手順は次のとおりです [これは実際のコードから変換された疑似コードなので、エラーが発生していないことを願っています]:
for z in 1..n:
prime[z] = false
prime[2] = true;
prime[3] = true;
for x in 1..sqrt(n):
xx = x * x
for y in 1..sqrt(n):
yy = y * y
z = 4*xx+yy
if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
prime[z] = not prime[z]
z = z-xx
if (z <= n) and (z mod 12 == 7):
prime[z] = not prime[z]
z = z-yy-yy
if (z <= n) and (x > y) and (z mod 12 == 11):
prime[z] = not prime[z]
for z in 5..sqrt(n):
if prime[z]:
zz = z*z
x = zz
while x <= limit:
prime[x] = false
x = x + zz
for z in 2,3,5..n:
if prime[z]:
if n modulo z == 0 then print z
于 2008-09-21T06:36:17.910 に答える
5
素因数分解ができたら、約数を見つける方法があります。個々の因数の各指数に 1 を加えてから、指数を掛け合わせます。
例: 36 素因数分解: 2^2*3^2 除数: 1、2、3、4、6、9、12、18、36 除数の数: 9
各指数に 1 を加算 2^3*3^3 指数を乗算: 3*3 = 9
于 2010-02-02T00:28:59.780 に答える
4
ソリューションにコミットする前に、Sieveアプローチは一般的なケースでは適切な答えではない可能性があることを考慮してください。
しばらく前に主要な質問があり、私は時間テストを行いました-少なくとも32ビット整数については、それがプライムであるかどうかをブルートフォースよりも遅くしました。進行中の2つの要因があります：
1）人間は分割を行うのにしばらく時間がかかりますが、コンピューター上では非常に高速です。答えを探すコストと同じです。
2）プライムテーブルがない場合は、L1キャッシュで完全に実行されるループを作成できます。これにより高速になります。
于 2009-07-18T04:11:54.253 に答える
4
これは効率的なソリューションです。
#include <iostream>
int main() {
int num = 20;
int numberOfDivisors = 1;
for (int i = 2; i <= num; i++)
{
int exponent = 0;
while (num % i == 0) {
exponent++;
num /= i;
}
numberOfDivisors *= (exponent+1);
}
std::cout << numberOfDivisors << std::endl;
return 0;
}
于 2014-12-01T14:01:19.630 に答える
3
除数は素晴らしいことをします: 完全に除算します。数値 の約数を確認したい場合、nスペクトル全体 をスパンするのは明らかに冗長1...nです。私はこれについて詳細な調査を行っていませんが、Triangular Numbers に関する Project Euler の問題 12を解決しました。500 を超える除数のテストに対する私のソリューションは、309504 マイクロ秒 (~0.3 秒) 実行されました。この除数関数をソリューション用に作成しました。
int divisors (int x) {
int limit = x;
int numberOfDivisors = 1;
for (int i(0); i < limit; ++i) {
if (x % i == 0) {
limit = x / i;
numberOfDivisors++;
}
}
return numberOfDivisors * 2;
}
どのアルゴリズムにも弱点があります。これは素数に弱いと思いました。しかし、三角数は印刷されていないため、その目的を完璧に果たしました。私のプロファイリングから、私はそれがかなりうまくいったと思います。
ハッピーホリデー。
于 2010-12-30T21:19:34.097 に答える
2
ここで説明されている Atkin のふるいが必要です: http://en.wikipedia.org/wiki/Sieve_of_Atkin
于 2008-09-21T05:53:17.577 に答える
1
素数法はここで非常に明確です。P[] は sq = sqrt(n) 以下の素数のリストです。
for (int i = 0 ; i < size && P[i]<=sq ; i++){
nd = 1;
while(n%P[i]==0){
n/=P[i];
nd++;
}
count*=nd;
if (n==1)break;
}
if (n!=1)count*=2;//the confusing line :D :P .
i will lift the understanding for the reader .
i now look forward to a method more optimized .
于 2013-01-09T23:12:36.013 に答える
1
以下は、与えられた数の約数を求める C プログラムです。
上記のアルゴリズムの複雑さは O(sqrt(n)) です。
このアルゴリズムは、完全平方数と完全平方数ではない数に対して正しく機能します。
ループの上限は、アルゴリズムを最も効率的にするために、数値の平方根に設定されていることに注意してください。
上限を別の変数に格納すると時間も節約されることに注意してください。for ループの条件セクションで sqrt 関数を呼び出さないでください。これにより、計算時間も節約されます。
#include<stdio.h>
#include<math.h>
int main()
{
int i,n,limit,numberOfDivisors=1;
printf("Enter the number : ");
scanf("%d",&n);
limit=(int)sqrt((double)n);
for(i=2;i<=limit;i++)
if(n%i==0)
{
if(i!=n/i)
numberOfDivisors+=2;
else
numberOfDivisors++;
}
printf("%d\n",numberOfDivisors);
return 0;
}
上記の for ループの代わりに、次のループを使用することもできます。これは、数値の平方根を見つける必要がなくなるため、さらに効率的です。
for(i=2;i*i<=n;i++)
{
...
}
于 2014-08-19T13:35:05.060 に答える
0
これは単に数を因数分解する、つまり数のすべての因数を決定するという問題ではありませんか? 次に、1 つ以上の要因のすべての組み合わせが必要かどうかを判断できます。
したがって、1 つの可能なアルゴリズムは次のようになります。
factor(N)
divisor = first_prime
list_of_factors = { 1 }
while (N > 1)
while (N % divisor == 0)
add divisor to list_of_factors
N /= divisor
divisor = next_prime
return list_of_factors
その後、要因を組み合わせて残りの答えを決定するのはあなた次第です。
于 2008-09-21T05:59:48.093 に答える
-1
最も効率的な方法はわかりませんが、次のことを行います。
- 素数の表を作成して、数の平方根以下のすべての素数を見つけます (個人的には、アトキンのふるいを使用します)
- 数の平方根以下のすべての素数を数え、2 を掛けます。数値の平方根が整数の場合、カウント変数から 1 を引きます。
\o/ 動作するはずです
必要に応じて、明日 C で何かをコーディングしてデモを行うことができます。
于 2008-09-21T06:16:10.627 に答える