webdevqa.jp.net

与えられた数の約数の数を計算するアルゴリズム

与えられた数の約数の数を計算するための最適なアルゴリズム(パフォーマンス面)は何でしょうか?

疑似コードまたはいくつかの例へのリンクを提供できれば素晴らしいことです。

編集:すべての答えは非常に役に立ちました、ありがとう。アトキンのふるいを実装してから、ジョナサンレフラーが示したものに似たものを使用します。ジャスティンボゾニエが投稿したリンクには、私が望んでいたものに関する詳細情報があります。

168
sker

ドミトリーは、あなたがアトキンのふるいにプライムリストを生成してほしいと思うのは正しいが、それが問題全体の面倒を見るとは思わない。素数のリストができたので、それらの素数の何が除数として機能するか(およびその頻度)を確認する必要があります。

アルゴリズム用のpythonがあります こちらをご覧ください および「Subject:math-need divisors algorithm」を検索します。ただし、リスト内のアイテムを返すのではなく、アイテムの数をカウントします。

これはDr. Mathです それは数学的に何をする必要があるかを正確に説明しています。

基本的には、あなたの番号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%確信はありませんが、そうでない場合は似たようなものです。

77
Justin Bozonier

lotアトキンのふるいよりも多くのファクタリング手法があります。たとえば、5893を因数分解する必要があるとします。そのsqrtは76.76です...ここで、5893を平方の積として記述しようとします。よく(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桁の数値を約.05秒で分解できます。 (あなたが疑問に思った場合、その因数分解は29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949です。Atkinのふるいを使用してこれを理解できなかったと確信しています...)

47
user11318

@Yasky

除数関数には、完全な正方形では正しく機能しないというバグがあります。

試してください:

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;
}
33
Kendall

アトキンのふるいが道であることに同意しません。なぜなら、[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コードを機能させています。

27
Tyler

この興味深い質問は見た目よりもはるかに難しく、答えられていません。質問は2つの非常に異なる質問に分けられます。

Nが与えられた場合、Nの素因数のリストLを見つける

2が与えられた場合、一意の組み合わせの数を計算する

私がこれまでに見たすべての答えは#1を参照しており、それが膨大な数に対して扱いにくいことは言及していません。適度なサイズのN、64ビットの数値でも、簡単です。膨大なNの場合、因数分解の問題は「永遠に」かかる可能性があります。公開鍵の暗号化はこれに依存します。

質問#2はさらに議論する必要があります。 Lに一意の数値のみが含まれる場合、n個のアイテムからk個のオブジェクトを選択するための組み合わせ式を使用した単純な計算です。実際には、kを1からsizeof(L)まで変化させながら式を適用した結果を合計する必要があります。ただし、Lには通常、複数の素数の複数のオカレンスが含まれます。たとえば、L = {2,2,2,3,3,5}はN = 360の因数分解です。この問題は非常に困難です。

アイテムaに重複があり、アイテムbにbが重複するなど、k個のアイテムを含むコレクションCを指定して#2を再設定します。1〜k-1個のアイテムの一意の組み合わせはいくつありますか。たとえば、{2}、{2,2}、{2,2,2}、{2,3}、{2,2,3,3}は、L = {2,2の場合にそれぞれ1回だけ出現する必要があります、2,3,3,5}。このような一意のサブコレクションはそれぞれ、サブコレクション内のアイテムを乗算することにより、Nの一意の除数です。

10
dongilmore

あなたの質問に対する答えは、整数のサイズに大きく依存します。少数のメソッド、例えば100ビット未満で、数値の場合(暗号化で使用されるような)〜1000ビットは完全に異なります。

9
jfs

これは単純なO(sqrt(n))アルゴリズムです。これを使用して project euler

def divisors(n):
    count=2 # accounts for 'n' and '1'
    i=2
    while(i**2 < n):
        if(n%i==0):
            count+=2
        i+=1
    count+=(1 if i**2==n else 0)
    return count  
8
Antony Thomas

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;
}

OR

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;
}

小さなは美しいです:)

これを試してみてください。それは少しハックですが、それはかなり高速です。

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
5
Michael

アトキンのふるいはエラトステネスのふるいの最適化されたバージョンであり、与えられた整数までのすべての素数を与えます。詳細については、これをグーグルで検索できるはずです。

そのリストが得られたら、数値を各素数で除算して、それが正確な除数(つまり、剰余がゼロ)であるかどうかを確認するのは簡単です。

数(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
5
paxdiablo

素因数分解ができたら、除数の数を見つける方法があります。個々の因子の各指数に1を加算し、指数を乗算します。

例:36素因数分解:2 ^ 2 * 3 ^ 2約数:1、2、3、4、6、9、12、18、36約数の数:9

各指数に1を追加します2 ^ 3 * 3 ^ 3指数を乗算します:3 * 3 = 9

5
D. Williams

ソリューションにコミットする前に、通常の場合、Sieveアプローチは適切な答えではない可能性があることを考慮してください。

しばらく前に素数の質問があり、タイムテストを行いました-少なくとも素数であるかどうかを決定する32ビット整数については、ブルートフォースより遅いです。次の2つの要因があります。

1)人間は除算に時間がかかりますが、答えを調べるコストと同様に、コンピューター上では非常に高速です。

2)プライムテーブルがない場合は、完全にL1キャッシュで実行されるループを作成できます。これにより、高速化されます。

3
Loren Pechtel

これは効率的なソリューションです。

#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;
}

除数は壮観なことを行います。完全に分割されます。数の除数の数nを確認する場合、スペクトル全体1...nにまたがることは明らかに冗長です。私はこれについて詳細な研究を行っていませんが、解決しました 三角数字に関するプロジェクトオイラーの問題12500を超える除数テストのソリューションは、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;
}

すべてのアルゴリズムには、弱点があります。これは素数に対して弱いと思いました。しかし、三角形の数字は印刷されないため、その目的を完璧に果たしました。私のプロファイリングから、かなりうまくいったと思います。

幸せな休日。

2
iGbanam

ここで説明されているアトキンのふるいが必要です: http://en.wikipedia.org/wiki/Sieve_of_Atkin

1
SquareCog

ケンダル

コードをテストし、いくつかの改善を行いましたが、今ではさらに高速になっています。また、@هومنجاویدپورコードでテストしましたが、これは彼のコードよりも高速です。

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}
1
as2d3

これが私が書いた関数です。最悪の時間の複雑さはO(sqrt(n))であり、最良の時間はO(log(n))です。すべての素因数とその出現回数を示します。

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}
1
Adilli Adil

以下は、与えられた数の約数の数を見つける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++)
{
    ...
}
1
Lavish Kothari

これは、数の除数を計算する最も基本的な方法です。

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}
1
Malik

数論の教科書では、除数カウント関数tauを呼び出します。最初の興味深い事実は、乗法的であるということです。 τ(ab)=τ(a)τ(b)、aとbに共通因子がない場合。 (証明:aとbの約数の各ペアは、abの異なる約数を与えます)。

Pが素数の場合、τ(p ** k)= k + 1(pのべき乗)に注意してください。したがって、分解からτ(n)を簡単に計算できます。

ただし、大きな数の因数分解は遅くなる場合があります(RSAクリプトラフィのセキュリティは、2つの大きな素数の因数分解が難しいことに依存します)。これは、この最適化されたアルゴリズムを示唆しています

  1. 数値が素数(高速)かどうかをテスト
  2. その場合、2を返します
  3. それ以外の場合、 数の因数分解 (複数の大きな素因数の場合は遅い)
  4. 因数分解からτ(n)を計算
1
Colonel Panic

ここでは素数法が非常に明確です。 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  .
1
abdelkarim

これは正確であると同時に便利だと思います

script.python

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

0
Syed Hissaan

これは単なる数の因数分解の問題ではありませんか?数のすべての要素を決定するのですか?その後、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

その後、要因を組み合わせて残りの答えを決定するのはあなた次第です。

0

これはジャスティンの答えに基づいて思いついたものです。最適化が必要になる場合があります。

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))
0
winsid96

最大可能Nの平方根まで素数を事前計算し、数のすべての素因数の指数を計算できます。 nの約数の数(n = p1 ^ a p2 ^ b p3 ^ c ...)は、(a + 1)(b + 1)(c + 1)です。これは、素数を結合する方法をカウントするのと同じだからですこの要素の数(およびこれは除数の数をカウントします)。素数を事前計算する場合、これは非常に高速です

この方法に関する詳細情報:

https://mathschallenge.net/library/number/number_of_divisors

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

http://primes.utm.edu/glossary/xpage/tau.html

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int divisors_count(const vector<int>& primes, int n)
{
    int divisors = 1;
    for (int i = 0; i < primes.size(); ++i) {
        int factor = primes[i];
        int factor_exponent = 0;
        while (n % factor == 0) {
            ++factor_exponent;
            n /= factor;
        }
        divisors *= (factor_exponent + 1);
    }
    if (n > 1) 
        return 2*divisors; // prime factor > sqrt(MAX_N)
    return divisors;
}

int main()
{
    const int MAX_N = 1e6;
    int max_factor = sqrt(MAX_N);

    vector<char> prime(max_factor + 1, true);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            for (int j = 3*i; j <= max_factor; j += 2*i) {
                prime[j] = false;
            }   
        }
    }

    vector<int> primes;
    primes.reserve(max_factor/2);
    primes.Push_back(2);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            primes.Push_back(i);
        }
    }

    int n;
    while (cin >> n) {
        cout << divisors_count(primes, n) << endl;
    }
}
0
izanbf1803

これらの線に沿って何かを試してください:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}
0
Bryant Jackson

これはあなたが探しているものだと思います。 Notepadにコピーして貼り付け、*。bat.Run.Enter Numberとして保存します。プロセスに2を掛け、それを除数の数とします。

Plsは、CMD可変変数は999999999を超える値をサポートすることに注意してください

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start
0
dondon