php - 特定の約数に対する最適アルゴリズム

Question

一意の約数を見つけるための最適なアルゴリズムの複製ではありません

この問題に遭遇しました。最適なアルゴリズムを見つけることができません。

問題は ：

L自然数のリスト (数値は非常に大きくなる可能性があります) と数値が与えられた場合、リストに存在する数値を分割しないN除数の数を決定するための最適なアルゴリズムは何ですか。リスト内の数値は反復することができます。つまり、1 つの数値が複数回出現する可能性があります。NL

観察：

の約数の約数は の約数dでNもありNます。

私のアプローチは：

1. の約数を求めNます。
2. L を逆順に並べ替えます (最大の要素が 1 番目の要素になります)。
3. のforeach 除数d、リストN内の要素を分割するかどうかをチェックします。d
4. dがリスト内のある数を除算する場合L、 の除数をチェックしませんd。つまり、このチェックをスキップします。
5. 最終的に、リスト内のどの数も除算もスキップもされなかった左除数がカウントされます。この数が最終的な答えです。

しかし、このアルゴリズムはこの問題には最適ではありません。

より良いアルゴリズムのアイデアはありますか?

Answer 1

<?php

class Divisors {
  public $factor = array();

  public function __construct($num) {
    $this->num = $num;
  }

  // count number of divisors of a number
  public function countDivisors() {
    if ($this->num == 1) return 1;

    $this->_primefactors();

    $array_primes = array_count_values($this->factor);
    $divisors = 1;
    foreach($array_primes as $power) {
      $divisors *= ++$power;
    }
    return $divisors;
  }

  // prime factors decomposer
  private function _primefactors() {
    $this->factor = array();
    $run = true;
    while($run && @$this->factor[0] != $this->num) {
      $run = $this->_getFactors();
    }
  }

  // get all factors of the number
  private function _getFactors() {
    if($this->num == 1) {
      return ;
    }
    $root = ceil(sqrt($this->num)) + 1;
    $i = 2;
    while($i <= $root) {
      if($this->num % $i == 0) {
        $this->factor[] = $i;
        $this->num = $this->num / $i;
        return true;
      }
      $i++;
    }
    $this->factor[] = $this->num;
    return false;
  }
} // our class ends here

    $example = new Divisors(4567893421);
    print $example->countDivisors();
?>

Answer 2

まず、n を素因数分解して次のように表します: p1:k1, p2:k2,..., pm:km p1,p2,... がすべて素数で n=p1^k1 * p2^k2 となるようにします。 ...

ここで、r1<=k1、r2<=k2、...、rm<=km となるように r1、r2、r3、...、rm を繰り返し、p1^r1*p2^r2...*pm かどうかを確認します。 ^rm は L の任意の数を割ります。そうでない場合は、count を 1 増やします。

最適化: r1 の値を選択します。p1^r1 が L の任意の数を割り切れるかどうかを確認します。割り切れる場合は、r2 の数を選択します。p1^r1 が L のどの数値も除算しない場合、count を (k2+1) (k3+1) ..*(km+1) だけインクリメントします。

例 N=72, L=[4, 5, 9, 12, 15, 20]: N を主積として書く: 2:3, 3:2 (2^3*3*2 = 72).

p1=2, p2=3, k1=3, k2=2
count=0
r1=0:
    r2=0:
        Divides 4
r1=0:
    r2=1:
        Divides 9
r1=0:
    r2=2:
        Divides 9
r1=1:
    r2=0:
        Divides 4
r1=1:
    r2=1:
        Divides 12
r1=1:
    r2=2:
        L not divisible by 18. Count+=1 = 1
r1=2:
    r2=0:
        Divides 4
r1=2:
    r2=1:
        Divides 12
r1=2:
    r2=2:
        L not divisible by 36. Count+=1 = 2
r1=3:
    r2=0:
        L not divisible by 8. Count+=(k2+1) +=(2+1) = 5

Answer 3

あなたが調べる必要があるのは、コプライム（または相対的素数）です。

整数論では、数学の一分野である 2 つの整数 a と b は互いに素である (co-prime とも呼ばれる)、または両方を等分する唯一の正の整数が 1 である場合に互いに素であると言われます。

したがって、問題を「トランスコード」するには：

N基本的に、リストから余素の数を見つけたいと考えていますL。

コプライムaはbいつですか？

2 つの数値が互いに素である場合、それらの最大公約数 (GCD) は 1 です。

PHP のコード例 (GCD 用):

<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>

簡単に言えば ：

• $count = 0
• eリスト内のforeach 要素L: を計算しますGCD(e,N)
• それらの GCD=1 ですか? はいの場合、それらは互いに素です (したがってN、公約e数はありません)。それを数えます。$count++

それだけです。