尋找獨特除數的最佳算法

Question

我只是在想一個似乎並不困難的問題，但是當我們想要做到最佳時，它就成了一個很好的問題。問題是 - 我們已經得到一個數字和一個數字N的列表（數組）。我們必須找到N的所有除數，它不會將屬於該列表的任何數字分開。我用蠻力和一點有效的方法解決了它（但不是最好的方法）。所以，我正在尋找一種解決這類問題的最佳方法。一切都以整數（無浮點）爲單位。每一個想法是讚賞。

我的做法是，我首先找到N的所有除數（沒有任何開銷）。然後，我按照相反的順序（單獨）對列表和除數進行排序。現在，對於每個除數D，我檢查它是否將列表中的任何數字分開（從最高元素開始到> =除數D的元素）。如果它分開，那麼D的所有因數也必須分開。然後，我從除數列表中刪除那些也是D的除數的元素（可以認爲是刪除交集）。因此，最終左邊的除數陣列是所需的數組（根據我的方法）。如果有人可以指出我的方法中的任何錯誤或缺乏效率，這是值得讚賞的。列表中可以出現的最大值是10^18。

我嘗試迄今在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; 
} 

Answer 1

一個明顯的優化是以下 - 做sieve of eratosthenes到fatorize所有數字高達你知道是高於任何單一的一個在你給出的列表中的值。現在您可以遍歷該列表中給定數字的所有因素。

你接下來要做的是：對於列表中的每個數字和它的每個素因子p，你應該除以p，直到N可以被它整除。在你這樣做之後，你所尋找的除數是餘數的所有除數。

希望這會有所幫助。