Question

I'm stuck on ps1a
How do I test if a particular candidate is prime? I understand that I need to check if there is a remainder when I divide by any integer>1, but how do I actually structure that test?

Answer 1

well the basic idea is to check all odd numbers before your number to see if any of them is a divisor
of course u dont need to test ALL but you can set a limit to it

Answer 2

Not only odd - 2 too. And up to a certain limit, which is way lower than the number you test.

Answer 3

forget the 2 the assignment requires that you filter the odds out first anyway so basically you start with 3, then do your if condition to see if there is a remainder for all the divisions up to the variable you#re trying to determine (for loop with a counter). if so it means prime if not break...hope it helps

Answer 4

@Beeb - The assignment doesn't require that you generate only odd numbers to test, it merely suggests it. Of course, testing only odd numbers would be more efficient. However, ps1b will require that 2 be included in the list of primes to get a correct answer.

@jaron - I've attached my ps1a, if you'd like to take a look. It is very inefficient, but it works.

Answer 5

Opps, sorry for the double post.

Answer 6

from an algorithmic efficiency point of view I find the filtering out of the evens quite a bonus and the 2 as a gain for not doing so not very important. One can just add it via append (see below)since it is an obvious simple prime case...and this is a program not a math course. Plus it makes the filtering a tad easier and the running through way more efficient.
Here is my old piece of code....

# prime.py
# finds primes up to 1000

list=[]
for k in range(1001): #since it would otherwise just go to 999 due to range
if ((k%2)==1): #takes the odd ones
for j in range(2,k+1): #loops through all variables from 2 to k
if( ((k%j)==0) and j<k): #checks if not prime and smaller than k (k being the number we are trying to test)
break #exits goes to next k (as far as I gather)
elif (not(k%j) and j==k): #if it is 0 for j==k it means it is prime (only then)
list.append(k)
print list

so try that do a print in between of the outputs to see what it is doing...., I do not have 1 and 2 in there but one can add them via list.append(1) same for 2 then they are there right after defining list.

Answer 7

One can simplify the number of divisor to go through by limiting the divisor to be other primes smaller than the current number. See the attach file for a way to do this.

Answer 8

i tried it and it didn't work ...it gave me only 2 many times and didn't stop

Answer 9

ranlab, Did you check to make sure your indentation is correct? e.g. the num+=2 statement is at the first level under the while and not inside the if.

Answer 10

oh sorry i tried it again now and it worked but i don't think we took this in lectures till now. I mean break and append...can you expalin the code please. Thanks a lot

Answer 11

ranlab, "break" is a statement that stops the current loop from going into the next iteration. In this case it stops the "for i in primes:" loop, NOT the "while count<1000:" loop. I used this as a shortcut way to stop additional iterations in the "for" loop, because we have just found a divisor that results in no remainder. The "append" method adds a element to the end of a list. So "primes.append(num)" adds "num" as the last element to list "primes".

Answer 12

ok thanks a lot. which lectures are you in or you finished python

Answer 13

I'm on lecture 22. But just started to work on the problem sets.

Answer 14

ok good luck...i thought we can study together but its way too far. i am in lecture 4 :D

Answer 15

Thank you all for the help. I am starting to understand the logic and wrote something that prints out some numbers...but the first one it gives is 21! What am I doing wrong here?

testNum = 3
y = 1000
while(y>0):
for i in range(2, testNum):
if testNum % i ==0:
print testNum
y = y - 1
testNum = testNum + 2
if testNum % i !=0:
testNum = testNum + 2
print testNum

Answer 16

An if after another based on variable changed in the first if could be your problem, so it fulfils the first if and then updates testNum and then questions testNum again which gets fulfilled maybe and adds again. If it goes directly to your second if and adds two to testNum then goes into your for loop again...leading to not finding the desired result.... I would suggest you put a print statement under every step so that you see the flawed logic and avoid two ifs in a row, do an elsif...also take a look at the prior codes posted to see how they use the variables they define.

Answer 17

hm...if you want to test x, if there's no divisor from 3 to x/2 -> x is a prime. Hope that helps :) you can also consider testing 2,3,5,7 to reduce the problem to 1/7.