寻找独特的除数优化算法 [英] optimal algorithm for finding unique divisors

问题描述

我当时就在想，这似乎并没有太大很难，但我们认为这样做最优化的，它成为一个相当好的问题一个问题。是 - 我们已被赋予号码列表（阵列），一个数N的问题我们必须找到N的所有的除数不分裂的任何数目属于该列表。我已经解决了它与蛮力和一点点有效的方法（但不是最好的）。所以，我在找这可能是最好的解决此类problem.Everything的方法是在整数计算（无浮点）。每一个想法是AP preciated。

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

我的努力到目前为止在PHP中：

 而（$格=每个（$除数））
{
$ 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;
}
 

解决方案

一个明显的优化是以下 - DO 筛埃拉托色尼的来fatorize所有的数字给你知道的是高于任何单一之一，你给出的列表中的值。现在，您可以遍历从该列表中给定数目的所有因素。

什么你接下来要做的就是：每个数字在列表中，每个质因子的P，你要分ň用p直到整除它。当你做，你正在寻找的除数剩余数的所有约数。

希望这有助于。

I was just thinking of a problem which does not seem to be much hard but when we think of doing it optimally, it becomes quite a good problem. The problem is- We have been given a list(array) of numbers and a number N. We have to 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). Every idea is appreciated.

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.

My attempt so far in PHP:

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

解决方案

One obvious optimization is the following - do sieve of eratosthenes to fatorize all numbers up to a value you know is higher then any single one in the list you are given. Now you can iterate over all the factors of a given number from that list.

What you do next is: for each number from the list and each of its prime factors p you should divide N by p until it is divisible by it. After you do that the divisors you are looking for are all divisors of the remaining number.

Hope this helps.

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