Question

Still stuck with PS1. I'm feeling disheartened, I've watched the first 3 lectures and read all related reading materials, but can't do PS1a, not to mention PS1b or PS2. I thought I had a good idea of using a for loop with range(3, numberbeingtested/2) which will work fine for checking divisors for numbers larger than 7, but it won't initialise for the first few small prime numbers.

Answer 1

Let's see. You need to generate all the prime numbers, from the first to the 1000th.
So, what would you do, if the assignment was "find the fifth prime?"

You would do something of the sort (brute force, not optimized):

You know that 2, 3 are primes. So you put them in your list-of-primes.
Since you know that 4 is not prime (even number), then you check 3+2 (= the biggest prime already found +2). Is it prime? If yes, you add it to your list-of-primes, and you ask whether: is your list composed by five elements already? (If the answer is yes, you stop because the last element in the list is the fifth prime). Otherwise (ie if 3+2 is not prime, or 3+2 is prime but your list is not made by five elements yet), you check 3+2+2.

I hope this helps you to build the structure of the code! Don't give up: learning to jot down the algorithms that you do in your head can be frustrating at the beginning. But you already know them! (The proof? You are surely able to find the fifth prime by hand!)

Answer 2

I think the 4th or 5th lecture talks about how to build a code. It shows you how to write down your thought process in simple terms (like a flow chart) before you actually write the code. Then you work out by hand what it's going to do and you can find obvious mistakes before you even open Python. This makes writing the code so much easier because you have created a road map. When I watched that lecture, my thought was "Oh- I wish I knew that when I was doing PS1."

Answer 3

I've seen that flow chart lecture, and I did VB.NET in High School, with flow charts and pseudocode. I still can't get this, if I have:

for divisor in range(3, primeTest/2):
Do Test

It won't initialise until testing number 7 (or 9, not sure). I don't know how to fix this.

This OpenStudy sucks, why can't I be the one to decide when my question has been answered?

Answer 4

paste your code to ideone.com or dpaste.com or .....
then post the link here

http://ideone.com/s4zrn

Answer 5

bwCA beat me to it. You should definitely post whatever you've got so far, no matter how ugly. Use dpaste.com or ideone.com so we can easily run your code.

And the medals that people award tend to highlight the correct answers. So if you get a bunch of different answers, then the one that got a lot of medals is probably closer to correct. Personally, I don't ignore an "answered" question.

Answer 6

Well, I don't really have any code, because I realised as soon as I wrote it that it won't run. But I guess this is what it would look like. http://ideone.com/S64ju

As far as I can tell, it starts working after 7, like I said.

Glad you don't ignore 'answered' questions but it's still a bit of a silly system.

Answer 7

Oh, I realised there are actually two problems: Firstly, it doesn't enter the for loop if values are less than 9, and I also can't figure out a way to test all divisors without incrementing primesFound incorrectly, or, as I have it at the moment, only testing the divisor 3 and then breaking out of the loop.

Answer 8

The for loop is not entered because you wrote range(3,primeTest/2). This means that until primeTest reaches 9, range(3,primeTest/2)=[]. No wonder that you do not enter the loop.

You test only 3 (the first divisor) because both branches (if / else) inside the for loop end with a break statement. Actually only the first element in range(3,primeTest/2) is ever tested, independently on the value primeTest/2, because as soon as the if statement is evaluated, independently on the answer you have a break statement that gives the control back to the while loop - which starts the thing all over again.

As far as the rest goes: this system might suck, but you must admit that in one day three people tried to help you out - which you should not discard as bad, after all. And liking the medal system or not, it is a matter of taste. My take, however, is that people who *already* solved a problem should be the ones more objective in assessing the quality of the answers concerning that problem.

Answer 9

If you're finding the problem too overwhelming, try solving an easier problem first. For example, just write the code that tests whether a single number is prime. Once you get your head wrapped around that problem, and get the code working to the point where you know exactly how it works, you can expand the task to finding several primes.

Also, don't worry about their suggested optimizations (only test odd numbers, only test odd divisors, only check divisors up to sqrt(n), etc) until you get a working solution. Once you get some code that works, SAVE A BACKUP OF YOUR WORKING CODE, then start making things work better. Make small changes, then test your changes to make sure you haven't broken anything.

As far as how to start writing any code at all, start with the absolute simplest thing that you can write and test, then test it and tweak it until it works. For testing whether a number is prime, first you're going to need to loop over some numbers to use as possible divisors. Write a loop that loops over some numbers and prints each number. Does it start at the right place? Does it stop at the right place? If not, figure out why, then fix it. Once THAT works how you expect, then do something simple but interesting inside the loop. Print the loop variable and the result of the operation. Is that what you expected? Etc. But always go from code that works to code that works, in small steps. Be slow and deliberate, and make sure you understand each step you take.

Answer 10

fra: You just restated exactly what I've been saying all this time. I don't know how to fix it.
and dmancine: Thanks, but I already know all that, I just can't work anything out.

Answer 11

You can't work anything out because you're trying to work everything out at once. You already have all the code around it to look for multiple primes, but your prime test code isn't working yet. It's not even iterating over the correct range of divisors. Start with a new file and write just the inner for loop, with just a debug print statement as the body. Make sure you get that to work (for several different numbers to test) before adding more code.

Here ( http://ideone.com/VAnEH) are the first 4 steps I took to do this problem. At each step I copied and pasted what I had previously before changing anything. (I put them into functions so I could include them all in one file. But I don't think we're supposed to use functions yet for PS1.) I commented the lines that changed at each step. Run each step and change numberToTest to several different values to make sure each step is working correctly.

Continue where I left off. Take small steps, keep previous versions of the code, test constantly. Implement just the algorithm that determines if a single number is prime. Eventually you'll have to add a boolean variable, isPrime, initialize it to True outside the for loop, and set it to False if you find a divisor. This is the "output" of this code. Post your code when you get this far. Only when you get that working for many different numbers (prime and composite) should you start writing the code around it that looks for multiple primes.

Answer 12

Why is this so ridiculously complex as the second problem set? Screw this, I'm gonna go learn elsewhere, or learn something else. Like French. Bye guys. Thanks anyway.

Answer 13

@ dmancine and fra, and the other helpers in this discussion area - thanks for you help. I am also stuck on this same problem and was thinking why is ps1a so hard - but you guys have made it seem much easier - I think this part of MIT OCW is great

Answer 14

Wow, Empowers is a really pretentious person... you know, the kind of person who is never wrong (it is always something else)... My guess is that he was rather smart but over praised as a child and then he learned that he is so smart that anything too hard for him is just not worth doing...

This is not such a complex problem and dmancine's tips are just fantastic and it's about how I did it.

I guess you are not supposed to be marvelously elegant with this problem, just provide a brute force solution...

I built a prime number generator then stored the numbers inside a list... which makes it so much more computable.

What would be interesting would be how to make it so that it is not necessary to check every odd number over 3... but I guess that is more of a math problem...

Answer 15

Maybe Empowers should choose a new handle.

@boids I'm glad my advice helped someone. I tried your proposal (don't check every odd number) and it turned out to be almost trivially easy. Here are my before ( http://www.ideone.com/rO3wg) and after ( http://www.ideone.com/QMOsu) shots.

Answer 16

boids - there are some probabilistic methods where you only check a random sampling of divisors. if you check enough of them, the probability of getting a wrong answer diminishes and becomes acceptable.
http://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests

Answer 17

@dmancine could not see your code (404 error)... I am really curious about it!

@bwCA your wikipedia reference is just "the answer" to my idea (I didn't know there was a wikipedia page with algorithms for finding primes). WOW.

Answer 18

I wonder if I'm posting my code with some sort of self-destruct setting. I'll try again.

First, this is all the steps I wrote up to try to help Empowers. Maybe others will want to see it. http://ideone.com/lOzb6

Next, here's my direct solution to PS1a: http://ideone.com/sj9Ee
And here's the one where I only check prime divisors: http://ideone.com/ag3TW

I didn't see any self-destruct checkboxes, so hopefully they'll last until you can see them.

Answer 19

Sorry, that last one isn't as efficient as it could be. Here's a better version of the code that uses the primes we already found to test for more primes. http://ideone.com/vC7bT

Answer 20

Well, I went away, I did things my own way, and ended up with really good simple code, using just the stuff learnt in the first 2 or 3 lectures, and it seems to be better than any of the other examples I've seen on here. The funny thing is, all I needed to know was one small piece of information to make it all work. So eat me, boids. I guess someone can't be pretentious if they have the talent to back it up. Here's my code for anyone needing help: http://ideone.com/PZFuU

Answer 21

Empowers, I'm glad you figured it out. And the beautiful part about this class is that we all get to do it our own way. I am constantly amazed to see how many different variations will give you the 1000th prime number. Really- people come at it from totally different angles. Any program that outputs the 1000th prime is successful. As we learn more we can make the solutions better and more elegant.

We are all here to learn. Personally I'm not interested in competitive programming... yet. But there are plenty of competitions elsewhere if that's your cup of tea.

You said your code "seems to be better than any of the other examples I've seen on here." You're not going to get much positive feedback in this group from goading the other members. The "one small piece of information to make it all work" that you needed could have come from this group, but the quality of the answers depends entirely on the quality of the question. Can I ask what that small piece of information was? I'm willing to bet it would help others (which is the goal of this group).

It sounds like you found the best way to learn for yourself. If the study group doesn't work for you or match up with your personal goals, then you don't have to use it. I find it amazingly helpful and an indispensable resource for my education.

Answer 22

@Empowers, I don't remember learning about for/else in the first 2 or 3 lectures.

Line 19, where you have to undo some work you didn't want to do, is inelegant. Can you think of a way to change the code so you don't need that kludge?

You're also testing even divisors for odd numbers. That seems inefficient.

I would also like to know the "one small piece of information." Was it un-indenting the else block?

Answer 23

@Empowers I called you pretentious because you said that this was "too difficult" just because you could not do it (which is assuming that everybody else is at least as incapable as you are and that most people will be unable to do it if you were unable to do it). It had nothing to do with you pretending to be very good in the sense of "being able to do it" but in the sense of "being better than most people here". And you have not disappointed me as you keep "being better than most people", as your solution "seems to be better than any of the other examples I've seen on here".

You just can't help it, can you?

Also, you said "The funny thing is, all I needed to know was one small piece of information to make it all work.", which means that it does not work, does it? I haven't tested it, I do not want to because you really are rude and pretentious and I do not care to help you in particular. You seem to believe that you are very smart so you will do fine without me.

Ok, I will take a look at your code... let's see.

Nice, it works.

Well, here is my version of it. It is not how I solved the problem, my solution is much more potent, modular and flexible but here is what I did to your solution to make it more elegant and easier to read (I also tuned the comments):

http://ideone.com/j0gEx

Also, my version of your solution has more mojo and is easier to debug, but who cares about that anyway?

So I am not eating you because I do not like you and I only eat stuff I like.

"I guess someone can't be pretentious if they have the talent to back it up.". Well, you can. You just did! That's being pretentious with the power of an ox!

Remember that you "did things your own way, and ended up with really good simple code, using just the stuff learnt in the first 2 or 3 lectures, and it seems to be better than any of the other examples you've seen on here." ? Well, that's being pretentious, even if you can solve the problem.

Believe me, you are not the first one to have solved the problem. But you knew that because you are never wrong. And you do not need "talent" to solve this problem, you just need to teach a computer how to find whether a number is prime, and then count every prime until it gets to the 1000th one and tell you what it is.

At least, solving this problem does not mean that you have the "talent" to say that your solution "seems to be better than any of the other examples I've seen on here".

Pretentious is not saying that you can do something when you actually can't. That's lying. Pretentious means that you like to show off and that you take yourself for someone who is more important and "better" than everyone else.

You think you are superior and solving this problem does not prove that.

Answer 24

Oh and btw, my code not only takes less lines and is easier to read, it goes almost twice as fast as yours.