Databases
StackOverflow2013
Postsdbo
POoptimal algorithm for finding unique divisors
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POoptimal algorithm for finding unique divisors
    primarykey
    data
    text
    <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.</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>My attempt so far in PHP:</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. USKara
    1. USSushant
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTDuplicate
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POoptimal algorithm for finding unique divisors
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POoptimal algorithm for finding unique divisors
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POoptimal algorithm for finding unique divisors
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCould you please show your effort here.
      singulars
      1. POoptimal algorithm for finding unique divisors
      1. USjames
 

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