可能重複:
optimal algorithm for finding unique divisors有效的方式來尋找獨一無二的除數
我以前也問過這個問題,但該帳戶目前無法訪問,所以我要求它再次表明我的這次的努力。
給出一個數字和數字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;
}
我在上一個問題中添加了相關的附加[與您的嘗試代碼對齊],並投票結束。 – amit 2012-04-08 09:46:04
@amit關於將問題轉交給http://codereview.stackexchange.com/怎麼樣? – 2012-04-08 09:49:12
@vitalik:(1)我不是主持人,只是一個編輯特權的人,所以我做不到。 (2)我認爲它不符合codereview.SE。他沒有要求審查,他完全要求採取不同的方法,並且提供了他以前的嘗試,因爲就像每個SO問題一樣,在提出問題之前預計會有一個體面的研究。 – amit 2012-04-08 09:51:06