anonymous
  • anonymous
Hi! There is an algorithm called the sieve of erastothenes to find a list of prime numbers on a list from 2 to n. I found an implementation of this algorithm saying that you need to iterate prove all the posible divisor from 2 to the square root of n. Why is that?
Mathematics
katieb
  • katieb
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

anonymous
  • anonymous
The reason taht I need to iterate from 2 to the square root of n, is a mathematical reason.
FoolAroundMath
  • FoolAroundMath
Consider any number 'x'. If you start iterating divisors from 2 onwards, say you get the following: I'll take an example case here, say 96 So, 96%2 = 0 and 96/2 = 48 So from one iteration of divisors which perfectly divides the given number, we get two divisors. Here in this case when we iterate for 2, we get two divisors 2, and 48. Next 96%3 = 0 and 96/3 = 32 So, 3,32 is another pair of divisors Note that with each pair, the 'distance' between the two divisors gets closer and closer. What is the limit of this difference? Clearly, if x is a perfect square, say 625 then the limiting case will be 625%25 = 0 and 625/25 = 25. Where the two divisors are the same. In the case of 96, [sqrt(96)]+1 = 10, so all we need to do is evaluate from 2 to 10. The factors of 96 are (2,48),(3,32),(4,24),(6,16),(8,12). Note that once we reach 10, any higher divisor that exists say for example 24 has already been discovered when we checked for x%4. Thus, it is sufficient to check only upto [sqrt(x)]+1 where [.] = smallest integer less than or equal to x Hence instead of iterating over all values from 2 to n-1 or 2 to n/2, we can simply iterate from 2 to sqrt(x).
anonymous
  • anonymous
I just read that I did not understand, but I will work on that thank you @FoolAroundMath =)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
Is this a mathematical equality[sqrt(96)] + 1 = 10?
ganeshie8
  • ganeshie8
yup.. [] is for integer value
FoolAroundMath
  • FoolAroundMath
[x] = the greatest integer that is equal to or less than x. http://en.wikibooks.org/wiki/Discrete_Mathematics/Sieve_of_Eratosthenes This link might help
anonymous
  • anonymous
ohh I didn't know that, that

Looking for something else?

Not the answer you are looking for? Search for more explanations.