有效的方式来寻找独一无二的除数

Question

可能重复：
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; 
} 

Answer 1

您可以使用此PHP implementation of the sieve of Eratosthenes。

还有this。

和this。

看一看this question。