A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

ps1b output: http://pastebin.com/PXHz4e2c 1. Does this look correct? 2. Do you see any areas in which I could make the code more efficient (either by doing less calculations or with fewer commands)? 3. How could I cleanly set it up to rerun until the user would like to exit? Thank you very much for paying it forward by giving me your thoughts. I just started, but hope to contribute here as I progress in the course. Cheers!

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

    First of all when you download to pastebin.com you can choose syntax. Choosing python syntax would make your code a lot easier to read.

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

    The algorithm you used seems to be correct. You use definition of prime in order to check if number n is prime. However, here's the output your program produced: This program will calculate the sum of the logs of all primes less than n and give their ratio relative to n. Note: n must be int > 2. n = 1000 The sum of the logs of primes > n is: 963.16198014 The ratio of sum of the logs to n is: 0.96316198014 So, what is the value of the 1000th prime? You seem to ask the user to input number n, and I entered 1000. But this is the number 1000, and then the program sums up the logs of primes with values less than 1000; the program doesn't calculate which number is the 1000th prime.

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

    Finally, there seems to be a bug somewhere since the sum of logs of all primes with values less than 1000 has to be 956.2453, I suppose, though I may be wrong. Have a look at my code here: http://pastebin.com/567ix4FU

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

    One more thing. Checking if a number is prime using definition of prime gets very slow when numbers increase. The "trial division" method seems to be better. You can check wikipedia to find the details.

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

    ...it is usually very helpful to have a look at other people's code :) this is how I initially got the idea to check other methods of checking primes: I looked at the code of another person and realized I had a very slow algorithm.

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

    Ah, thanks for the tip about pastebin formatting! Good suggestion about "trail division." That is a really clever way to improve efficiency. I'm just looking at ps1b, so this code isn't attempting to output the nth prime number, just the sum of logs of primes < n. I'm trying to figure out why we get different sum of logs of primes...

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

    The algorithms for finding the n-th prime and the sum of logs of primes from 0 to any number N (not the number of primes but a natural number) are very similar. When I did problem 1 I actually wrote very inefficient program in the beginning and then I looked at other people's solutions and, actually, reread the assignment, and, finally added more efficient code and made the program do what the assignment asked for :) Here is everything I wrote with some code commented out: http://pastebin.com/dc03ttGP There is a useful peace of code in the end. It allows to print a list of all prime number from 0 to whatever. The list can then be compared to the list in the web given in the assignment.

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

    Hi. You're algorithm seems good, but there is one bug there that is causing you to output the wrong sum of logs for primes less than n (for certain values of n). The problem is that your program is not stopping when it should but actually going on to find one more prime than you want and then adding the log of that to your sum before exiting. The largest prime below 1000 is 997, so your next candidate becomes 999 which is less than 1000 so it restarts your loop.

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

    Also, one way to make your program faster is to reduce the amount of divisors that you are checking, right now you are checking all possible divisors from 2 to (n-1). A simple way to reduce this is to only check divisors that are less than half of the candidate. You can do this in your code by swapping out "divisor = candidate - 1" with "divisor = candidate//2" (make sure to use // for integer division or else you will get a float).

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

    Hi, Wouldn’t it be more efficient to only check odd numbers?

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

    you're right, it would :)

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