php - 特定除数的最优算法

Question

不是寻找唯一除数的最佳算法的重复

我遇到了这个问题。我无法找到最佳算法。

问题是 ：

给定一个L自然数列表（数字可以非常大）和一个数字N，确定除数的数量N不会除以列表中存在的任何数字的最佳算法是什么L。列表中的数字可以是重复的，即一个数字可以出现不止一次。

观察：

的某个除数d的除数N也是 的除数N。

我的方法是：

1. 求 的除数N。
2. 以相反的顺序对 L 进行排序（最大的元素是第一个元素）。
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, r2, r3,..., rm 使得 r1<=k1, r2<=k2, ..., rm<=km 并检查 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

您需要研究的是：共素数（或相对素数）

在数论（数学的一个分支）中，两个整数 a 和 b 被称为互质数（也拼写为互质数）或互质数，如果唯一能将这两个整数整除的正整数是 1。

所以要“转码”你的问题：

您基本上想N从L列表中找到互质数。

什么时候a和b是共同质数？

如果两个数互质，则它们的最大公约数 (GCD) 为 1

PHP 中的示例代码（用于 GCD）：

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

简单的说 ：

• $count = 0
• eforeach列表中的元素L：计算GCD(e,N)
• 他们的 GCD = 1 吗？如果是，它们是互质的（所以N没有e公约数）。数一数。$count++

这就是它的全部。