Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

No-data

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?

  • one year ago
  • one year ago

  • This Question is Closed
  1. No-data
    Best Response
    You've already chosen the best response.
    Medals 0

    The reason taht I need to iterate from 2 to the square root of n, is a mathematical reason.

    • one year ago
  2. FoolAroundMath
    Best Response
    You've already chosen the best response.
    Medals 2

    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).

    • one year ago
  3. No-data
    Best Response
    You've already chosen the best response.
    Medals 0

    I just read that I did not understand, but I will work on that thank you @FoolAroundMath =)

    • one year ago
  4. No-data
    Best Response
    You've already chosen the best response.
    Medals 0

    Is this a mathematical equality[sqrt(96)] + 1 = 10?

    • one year ago
  5. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 0

    yup.. [] is for integer value

    • one year ago
  6. FoolAroundMath
    Best Response
    You've already chosen the best response.
    Medals 2

    [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

    • one year ago
  7. No-data
    Best Response
    You've already chosen the best response.
    Medals 0

    ohh I didn't know that, that

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.