快捷的方式找到独特的除数 [英] efficient way to find unique divisors

问题描述

  

可能重复：
  <一href="http://stackoverflow.com/questions/10061108/optimal-algorithm-for-finding-unique-divisors">optimal算法寻找独特的除数

我也问过这个问题之前，但该帐户是不能访问了，所以我再次要求它显示我的努力，这个时候。

给定号码和数量为N的列表（阵列），发现N的所有的除数不分裂的任何数目属于该列表。我已经解决了它与蛮力和一点点有效的方法（但不是最好的）。所以，我在找这可能是最好的解决此类问题的方法。一切都在整数计算（无浮点）。

我的方法，这是我第一次发现的数N的所有约数（没有任何开销）。于是，我对列表进行排序，并以相反的顺序（单独）的约数。现在，对于每个除数D，I是否将在所述的列表中的任何数目（从最高元素开始高达是> =所述因数D的一个元素）。如果分，那么D的所有分频器也必须分开。然后，我从除数这也是D的除数的列表中删除这些元素（可以认为是去掉了路口）。因此，最终的除数的左侧阵列（按照我的方法）所需的阵列。如果有人可以指向任何故障或任何在缺少我的方法的效率，这是美联社preciated。最大值可以是present列表为10 ^ 18。

我在PHP实现它。我提供我下面的code。请忽略注释。

 而（$格=每个（$除数））
{
$ i = 0;
$除数= $ DIV ['关键'];
//回声除数为$除数\ N的;
而（（INT）$不友好[$ i]＆GT; = $除数）
{//回声绫\ N的;
    如果（！（（INT）bcmod（$不友好[$ i]，$除数）））
    {//回声ayeea \ N的;
        $ divisors_of_divisor = divisors_of_a_number（$因子）;
        //的print_r（$ divisors_of_divisor）;
        //的print_r（$除数）;
        的foreach（$ divisors_of_divisor为$ D）
        取消设置（$除数[$ D]）;
        //的print_r（$除数）;
        打破;
    }
    ++ $ I;
}
 }
回声的sizeof（$除数）;
功能divisors_of_a_number（$ N）//返回一个数字的所有约数在排序的数组
{
$ i = 1;
$ S =开方（$ N）;
而（$ I＆LT; = $ S）
{
如果（！（$ N％$ I））
{
    $ A [] = $ I;
    如果（$ I！= $ S）
    $ A [] = $ N / $ I;
}
++ $ I;
}
返回$ A;
}
功能divisors_of_a_number_as_keys_of_array（$ N）//返回一个数字的所有因数中一个未排序数组作为键
{
$ i = 1;
$ S =开方（$ N）;
而（$ I＆LT; = $ S）
{
如果（！（$ N％$ I））
{
    美元[$ i] = 1;
    //如果（$ I！= $ S）
    美元[$ N / $ I] = 1;
}
++ $ I;
}
返回$ A;
}
 

解决方案

您可以使用此 PHP实现埃拉托色尼的筛。

和也这。

和这。

看看到这个问题。

Possible Duplicate:
optimal algorithm for finding unique divisors

I have asked this question before, but that account is not accessible now, so I am asking it again showing my effort this time.

Given a list(array) of numbers and a number N, find the all the divisors of N which doesn't divide any number belonging to the list. I have solved it with a brute force and a little efficient approach(but not the best one). So, I am looking for an approach which could be the best in solving this kind of problem. Everything is in terms of integer(no floating points).

My approach to this is that I first find all the divisors of the number N(without any overhead).Then, I sort the list and the divisors in reverse order(separately). Now, for each divisor D, I check if it divides any number in the list(starting from the highest element upto an element which is >= the divisor D). If it divides, then all divisors of D must also divide. Then I remove those elements from the list of divisors which are also the divisors of D(can be thought of as removing the intersection). So, ultimately the left array of divisors is the required array(according to my approach). If someone can point any fault or any lack of efficiency in my approach, it is appreciated. The max value which can be present in the list is 10^18.

I have implemented it in PHP. I am providing my code below. Please ignore the comments.

while($div=each($divisors))
{
$i=0;
$divisor=$div['key'];
//echo "divisor is $divisor\n";
while((int)$unfriendly[$i]>=$divisor)
{//echo "aya\n";
    if(!((int)bcmod($unfriendly[$i],$divisor)))
    {//echo "ayeea\n";
        $divisors_of_divisor=divisors_of_a_number($divisor);
        //print_r($divisors_of_divisor);
        //print_r($divisors);
        foreach($divisors_of_divisor as $d)
        unset($divisors[$d]);
        //print_r($divisors);
        break;
    }
    ++$i;
}
 }
echo sizeof($divisors);
function divisors_of_a_number($n)//returns all the divisors of a number in an unsorted array
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[]=$i;
    if($i!=$s)
    $a[]=$n/$i;
}
++$i;
}
return $a;
}
function divisors_of_a_number_as_keys_of_array($n)//returns all the divisors of a number in an unsorted array as keys
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[$i]=1;
    //if($i!=$s)
    $a[$n/$i]=1;
}
++$i;
}
return $a;
}

解决方案

You can use this PHP implementation of the sieve of Eratosthenes.

And also this.

And this.

Take a look to this question.

这篇关于快捷的方式找到独特的除数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！