Databases
StackOverflow2013
Postsdbo
POefficient way to find unique divisors
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POefficient way to find unique divisors
    primarykey
    data
    text
    <blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="https://stackoverflow.com/questions/10061108/optimal-algorithm-for-finding-unique-divisors">optimal algorithm for finding unique divisors</a> </p> </blockquote> <p>I have asked this question before, but that account is not accessible now, so I am asking it again showing my effort this time.</p> <p>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). </p> <p>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.</p> <p>I have implemented it in PHP. I am providing my code below. Please ignore the comments.</p> <pre><code>while($div=each($divisors)) { $i=0; $divisor=$div['key']; //echo "divisor is $divisor\n"; while((int)$unfriendly[$i]&gt;=$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&lt;=$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&lt;=$s) { if(!($n%$i)) { $a[$i]=1; //if($i!=$s) $a[$n/$i]=1; } ++$i; } return $a; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USuser1320006
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTDuplicate
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POefficient way to find unique divisors
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POefficient way to find unique divisors
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POefficient way to find unique divisors
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI am adding the relevant addition [the code snap with your attempt] to the previous question, and voting to close.
      singulars
      1. POefficient way to find unique divisors
      1. USamit
    2. CO@amit what about tranferring the question to http://codereview.stackexchange.com/ ?
      singulars
      1. POefficient way to find unique divisors
      1. USVitalij Zadneprovskij
    3. CO@vitalik: (1) I am am not a moderator, just a guy with editting privilliges, so I cannot do it. (2) I do not think it fits codereview.SE. He is not asking for a review, he is asking for a different approach completely, and is providing his previous attempt, since like every SO question, a decent research is expected before asking a question.
      singulars
      1. POefficient way to find unique divisors
      1. USamit
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload