p-set1-> How to check if a number is prime?
more specifically how do I get this into python language ? divisor = any number from 2 to (candidate-1)
Here is what I have so far- while candidate <40: candidate+=1 divisor+=1 if candidate>1 and candidate%2!=0: print candidate
Thank you so :)
why are you checking candidate%2? That will only tell you whether it is odd or even, not whether it is prime. Can you think of all the criteria required for a number to be prime?
Right, I am narrowing it down. A prime number is odd, greater than 0, and is not fully divisible by another integer. I am having trouble putting the syntax and semantics together for the last part- not divisible by another integer
well, 2 is a prime number, and it is not odd.
lets write some pseudo code: suppose you are trying to determine whether a number n is prime or not, the steps you need to follow: 1: check whether it is greater than 0, or if you assume 2 to be the first prime number, check whether it is greater than 2. n>0(or 2) 2: check whether it is divisible by 2. that will get rid of all the even numbers. 3: for any number k < n, check whether n is divisible by k. if yes: it is not prime if no: it is prime There are a few things you could do to optimize this code. What if n is a large number? you have to check for all the numbers less than n. Can you think of some way to reduce the number of values you check (i.e , number of k values)?
In step 3, I should have said for ALL values of k < n, not any.
candidate = 0 # Candidate prime number divisor = 2 # "k" as you defined it while candidate <10: # 10 is arbitrary ( just so I can find prime numbers below 10, first) candidate+=1 if candidate>1 and candidate%2!=0: while divisor < candidate: if candidate%divisor == 0: false else: divisor+=1 print candidate # to give me an output
I am getting incorrect outputs. Thank you for your patience and continued help
you said : while divisor < candidate: if candidate%divisor == 0: false if you do not increment your divisor here, you will be forever stuck in the while loop.
there is one more thing you could do. You can assume that 2 is the first prime number and then start with 3. After that you need to increment your candidates by 2 instead of 1. That way you will only check odd candidates, since 2 is the only even prime number. and while you are checking whether a number is prime or not, it is sufficient to show that all the numbers from 2 to sqrt(number) are not divisible by that number.
in fact, you can increment the divisors by 2 too, since if say, 17 is not divisible by 2, there is no way it is divisible by 4, so after 2, there is no point checking any of the other even numbers.
aghh After fighting with this problem for 3 hours... Still nowhere... I keep getting double answers. The problem is I do not know how to break it down properly. I can write down the pseudo code and I understand it well, but I just cannot get it into python- very frustrating. Gonna go eat now lol
Okay I finally figure it out- def isprime(number): for divisor in range(2,int(number**0.5)+1): if number%divisor== 0: return False return True count =0 candidate =1# So its every odd number when I add by 2 while count<1000: if isprime(candidate): count+=1 if count == 1000: print candidate candidate+=2
Now, I actually got some of the code from a website, and a little bit from another person's work. The only part I did "by myself" is figure out the counting mechanism and how to print the 1000th number. My question is- was this the right method to figuring out the answer? Or should I have derived it "all by myself" without looking anywhere for help. To be honest, if it was at school I would have gone to the recital and asked questions there anyway...
Well, the important thing is to figure out the pseudo code. Syntax is not as important. As long as you know the flow of control in the program, you are good. You can get help the first few times, but it is always better to figure it out by yourself. You can only learn from your own mistakes, not someone else's :)
Join our real-time social learning platform and learn together with your friends!