A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Here is my code for 1a. What do you guys think? Could it be more efficient? http://dpaste.com/hold/534504/

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    in your algorithm you don't have to go all the way up to the candidate number. You can go to (n/2)+1 to cut down on computation

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    consider divisors up to (n/2)+1 should speed it up

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you only need to go to sqrt(n) careful - optimizing early to the dark side leads kepp this under your pillow: http://wiki.python.org/moin/PythonSpeed/PerformanceTips

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How come the divisors only need to go up to (n/2)+1?

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If there is a divisor bigger than n/2 + 1 how many times would it go into the candidate number? Less than 2 (i.e. 1) which means the divisor is the candidate number itself. The logic for only going up to sqrt(n) is that if a number has any factors then at least one of them must be bigger than sqrt(n). Think about trying to factorise n as x*y where both x and y are less than sqrt(n). Say you were testing the number 12, you would never get as far as finding that 6 or 4 were factors but that doesn't matter becuase you would have found 2 (12/6) and 3 (12/4) before getting up to the square root. Worst case would be a number that is the square of a prime e.g. 25 where you won't find any factors until you reach the square root.

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.