Databases
StackOverflow2013
Postsdbo
POoptimal algorithm for particular divisors
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POoptimal algorithm for particular divisors
    text
    copied!<p><strong>Not a duplicate of-</strong> <a href="https://stackoverflow.com/questions/10061108/optimal-algorithm-for-finding-unique-divisors">optimal algorithm for finding unique divisors</a></p> <p>I came across this problem. I am not able to find an optimal algorithm. </p> <p><strong>The problem is :</strong></p> <p>Given a list <code>L</code> of natural numbers(number can be really large) and a number <code>N</code>, what's the optimal algorithm to determine the number of divisors of <code>N</code> which doesn't not divide any of the numbers present in the list <code>L</code>. Numbers in the list can be repetitive ie, one number can occur more than once.</p> <p><strong>Observation:</strong></p> <p>Divisors of some divisor <code>d</code> of <code>N</code> are also divisors of <code>N</code>.</p> <p><strong>MY approach was :</strong></p> <ol> <li>Find the divisors of <code>N</code>.</li> <li>Sort L in reverse order(largest element being 1st element).</li> <li>foreach divisor <code>d</code> of <code>N</code>, I check whether it divides any element in the list or not.(stop when you come to check for an element less than <code>d</code> in the list, as the list is sorted)</li> <li>If <code>d</code> divides some number in the list <code>L</code>, then I don't check for any divisor of <code>d</code>, that is, I skip this checking.</li> <li>Ultimately, left divisors which were neither divided any number in the list nor skipped are counted. This count is the final answer.</li> </ol> <p>But this algorithm is not optimal for this problem. </p> <p>Any ideas for a better algorithm?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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