Question

In problem set one I wrote this program to figure out if a number is prime but im doing something wrong.
x = 2437
y = 2
counter2 = y
while(x%counter2 > 0):
if counter2 < (x/2): counter2 = counter2 + 1
else: print x, "is a prime number"
print x, "is not prime."

Answer 1

The first thing I notice is that it is an infinite loop.

Once the program determines that a number is a prime, it keeps looping, printing
'x is a prime number.'

You need to find a way to break out of the loop once it finds it is a prime.

Answer 2

Python has a break statement which ends the loop.
http://www.network-theory.co.uk/docs/pytut/breakandcontinueStatements.html

Answer 3

solved it with this:

x = 239
y = 2
counter2 = y
while((counter2 < x/2) and (x%counter2 !=0)): #first part is making sure time isnt wasted
#with doing extra math, second part checks for prime
counter2 = counter2 + 1
if x%counter2 ==0:
print x, "is not prime"
else: print x, "is prime"

is there a better way to program this?

Answer 4

yours works so that's a good way to do it!
there are lots of ways to do this - here is a different (not necessarily better) way using the range function: http://pastebin.com/ALHXXtyF
there are two ways to optimize that;
at line three you could limit the range to the square root of x
at line 6 you could add a break statement to stop testing once you know it is Not prime
but, it works without the optimizations

http://docs.python.org/tutorial/controlflow.html#the-range-function

Answer 5

thanks for the reply bwca...one question. Isnt a break unnesseraily becuase i added the condition AND meaning as soon as it figures out the number is not prime the while function becomes negated?

Answer 6

not sure if this is a better way, but here's what I came up with using range() as well:

primeSought = 1000
numPrimes = 2 # number of primes so far
for number in range(4, 10000): # increase upper range if seeking higher prime
for x in range(2, number):
if number % x == 0:
break
else:
# nothing divides into the number--it is a prime
numPrimes = numPrimes + 1
if numPrimes == primeSought:
print number, 'is prime number',numPrimes,'\n'

this probably puts a little more work on the processor, but it does allow you to select for other prime numbers, if for some strange reason you actually wanted to do this :)

Answer 7

An optimisation I haven't seen mentioned is after you've tested if your number is divisible by 2, you then only need to test if it's divisible by odd numbers. So you'd have a test with counter2 = 2 before the while loop, set counter2 = 3, then inside the loop have
"counter2 += 2" instead of "counter2 = counter2 + 1".

As a side note, you only need to divide by all primes <= sqrt(x) to know if x is prime.

Answer 8

Also, I noticed your code fails for x = 1 and 2. To clarify, 1 is not prime and 2 is prime.

Answer 9

erthbound0: yep - your while loop will stop when either
counter2 is one-half of x or
you find that x is not prime

Answer 10

y'all should start using a code pasting site to post your code:
pastebin.com, dpaste.com, codepad.org, ideone.com - i bet there are a zillion of them