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.
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.
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.
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
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.
...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.
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...
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.
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.
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).
Hi, Wouldn’t it be more efficient to only check odd numbers?
you're right, it would :)