Question

Question ps1: I've unsuccessfully tried to come up with a program that checks whether or not a single number is prime. How do I check if a number is prime? Should I be dividing the number by every positive integer up to it's square root?

Answer 1

That is one way to do it. Post your attempt to codepad.org so I can see how you've tried.

Answer 2

A prime number is only divisible by 1 and itself. One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime.. now put what I just said in code and you got your problem solved ;)

Answer 3

x = number
found = false
for y = 2 to sqrt(x)
if x mod y = 0 then found = true
end the for loop

if found = false then prime
else not prime

you could also have a while loop that involves found so that you don't have to keep trying once it found a prime number

Answer 4

I got around to the PS1 P1, this is what I came up with:
http://pastie.org/2746902
Hope it is of any help to you
I hope I didn't overly complicate things.. but I couldn't really think of a more efficient way of doing things

Answer 5

P.S I took a more hands on approach instead of the math.sqrt(number) method

Answer 6

I can't understand how you got that with only the first two lectures and readings. I've done all the readings carefully and watched lec 1 and 2.
I think maybe I didn't understand the readings properly. What part should I focus on in the readings because I really can't follow what you are doing in your code.

Answer 7

oh, I have some previous experience in programming and that helped me a bit.. but I used to work in C#, hence my syntax in python is not that good (that's why I did the +' '+ instead of the ,

Answer 8

ahh, ok. thanks for trying to help!

Answer 9

read the tutorial and concetrate on the flow control section
http://docs.python.org/tutorial/
http://docs.python.org/tutorial/controlflow.html#more-control-flow-tools
and all of those readings for lectures 1-3 are good
variables, loops , conditional statements

Answer 10

PaulGillett- This is the first programming class I've ever taken (aside from a BASIC class in 6th grade, but I hardly think that counts). I had trouble finding how to code the first set, so I kept reading and watching lectures until I could write a code. Once I solved PS1, I found that I could do PS2 right away. Nothing bad happens if you keep reading & watching videos until you feel like you can attack the problem sets. The syllabus was for the graded class but we're free from those constraints.

One of the later lectures (arg- I can't find it right now!) talks about writing out what you want the code to do in plain English and then in flow charts. You work out the math by hand. Then once you've got a good idea of what the steps are, you write the code. (Personally I was annoyed they waited so long to introduce that concept- would have saved me hours of pointless wheel spinning.)

So you understand the math. Go ahead and type some ugly stuff into Python. Post it here and then we can help you over the initial hump.

Answer 11

if x%y == 0, then x is not a prime

Answer 12

Hey everyone, I think you guys are all great! With out the support and encouragement of all the people on this forum I probably would have given up on this problem a while ago. I guess programming is some tricky stuff. And Julie, you did basic programming in grade 6?!!? Wow, for a 27 year old, I may be starting programming a little late.

Anyhow, rock on everyone :)

Answer 13

keep at it! it's never too late.. I got 2 bachelor degrees (in economics and political science) before I realized that what I actually want to do is programming.. anyhow Julie is right, you shouldn't limit yourself to the 1st 2 lectures and readings if you feel you can't do this, actually I'd like to add that you shouldn't limit yourself to the course for doing this, Google is your friend and there are a ton of websites that will give you tutorials and answers, use everything you have at your disposal in order to learn

Answer 14

there is no age to grasp programming like there is to learn a musical instrument it takes practice I taught myself without any courses and now I'm in college and the stuff is very easy it took my about a year to grasp it concretely. I suggest you learn programming like operators and operand and functions before you try and digest a problem like solving a prime number

Answer 15

It's most efficient to just check prime divisors up to and including sqrt(n), but that's irrelevant. Go ahead and check every divisor from 2 to n (excluding n). Just get it to work, first, then you can worry about making it work better.

As far as how to start writing a program, work on something really easy first. The first goal you should have is to write a program that tests whether a single number is prime. Once you get that working you can worry about finding many primes.

But you should start out really simple. Like initialize a variable to the value you want to test for primeness. Then print out the value of that variable. Did that test pass? If so then add a for loop that loops from 2 to n-1 (divisors to test). Inside the loop print out the value of the divisor. Test it. Are you looping over the right numbers? If so then calculate num%divisor inside the loop, and print num, divisor, and num%divisor. Run it. Does the output make sense? Is it what you expected? Etc.

Take small steps. If you get confused or overwhelmed, take smaller steps. Do one step at a time, and test after each step. And make sure the tests pass. At this stage your tests involve printing something out, and you verifying the output is correct. Always read the output carefully to make sure you haven't assumed something that's not true.

Before you make a change you can even copy your old code, comment it out, then make the change on the copy. If you break something you can look back at what was working before and see what you messed up. When the new version works, throw away the old version and make a copy of the new version. (Or keep copies of all the old versions. Storage is cheap.) Repeat.

Go slow
Make changes deliberately
Test every change
Save copies of working code

Answer 16

Oh. And the only way to learn programming is to do it. You can read about it, and read other peoples' solutions to problems, but you'll never learn as much as by toughing it out. Going from understanding a problem to devising a solution, to turning the solution into code, to turning the code into working code is a process that takes practice to learn. It'll be tempting, but only look at other peoples' solutions once you're good and stumped. And then it's better to post your own code so we can diagnose where the misunderstanding is. Most people here are pretty good about trying to understand someone's code, and give hints to get them back on track, instead of just fixing it for them. That's important.

Answer 17

This is what I came up with when attempting this.
I just skipped even numbers by adding 2
also only divide by odds because if 2 wont divide it other even will not
I stop dividing at half the number because after that point none will work

x = 3 #starting at 3 to skip the 2 being prime problem
count = 1 # starting the count at 1 to account for prime 2 being skipped
while (count < 1000): # this will keep running until the 1000th prime is found
z = 3 # start at 3 because skipping evens so none will dev by 2
while(x%z > 0): # keep trying until x divides by z evenly
z = z + 2 # z adds 2 to only try by odd's
if z > (0.5*x): # stop at half of x's value beyond that none will work
count = count + 1 #add 1 for each prime found
x = x + 2 # add 2 to number tested to skip even's
print (x - 2) # print the 1000th prime found.

Answer 18

@EricKo and Amberdark, Please don't just post answers. I know you're proud of your work, and the OP can learn from seeing your code, but the best way for someone to learn programming is to figure it out on their own. Even if they ask for help it's better to try to just correct their misunderstandings, or point them in the right direction, than write code for them. Having said that, I know the OP didn't actually post any code, so it's hard to know how to help him, but maybe wait for him to ask more specific questions, or ask him some questions to try to understand his problem better.