# Python program to verify primes

1. Jan 23, 2012

### llstelle

1. The problem statement, all variables and given/known data
I'm supposed to write a program which asks for an integer input, then determines if the input is a prime or not.

I wrote a program but I have 2 issues:
1) It works well for primes up to around the size of 30000~, then above that (I just tried 65537, for a weak upper bound) it just freezes... I'm guessing Python has some memory allocation issue here? Is there a solution?
2) I don't like my code. It looks ugly. Having so many nested conditionals is not elegant. And so on. Are there any tips to improve what I have written? Thanks!

2. The attempt at a solution

Here's my code...

Code (Text):

#This program verifies if an integer is prime.

import time

x = int(raw_input('Please enter an integer.\n'))
if x == 2:
print ('2 is a prime')
elif x < 2:
print (str(x) + ' is not a prime.')
elif x > 3:
i = 2
while True:
j = x%i
if j == 0:
print(str(x) + ' is not a prime.')
time.sleep(5)
break
elif j != 0:
if i > x/2:
print(str(x) + ' is a prime.')
time.sleep(5)
break
elif i < x/2:
i = i+1

Last edited: Jan 24, 2012
2. Jan 24, 2012

### llstelle

OK I solved my first question, I had a mistake with the elif conditions... Here's the new code:

Code (Text):
#This program verifies if an integer is prime.

import time

x = int(raw_input('Please enter an integer.\n'))
if x == 2:
print ('2 is a prime')
elif x < 2:
print (str(x) + ' is not a prime.')
else:
i = 2
while True:
j = x%i
if j == 0:
print(str(x) + ' is not a prime.')
time.sleep(5)
break
elif j != 0:
if i > x/2:
print(str(x) + ' is a prime.')
time.sleep(5)
break
else:
i = i+1
But I'll still appreciate if someone can let me know what improvements can be made. (:

3. Jan 24, 2012

### rcgldr

Instead of "time.sleep(5)", you could use "raw_input('press enter to exit program')" to allow the user to see the results until enter is pressed before the dos console window closes.

The next two possible changes are related to knowledge of prime numbers, not of programming methods.

You could change "if i > x/2" to " if i*i > x", since there's no need to test for any prime number greater than the square root of x.

You could add a check for all even numbers, by replacing "elif x < 2", with "elif x < 2 or 0 == x%2", then start with "i = 3", and use "i = i + 2". This takes a bit more code, but reduces the number of iterations. I don't know if this would be considered more "elegant", since it's a bit more code, and modern computers are so fast that speed isn't an issue in this case.

Last edited: Jan 24, 2012
4. Jan 25, 2012

### llstelle

Ah thanks for the explanations! It was really helpful. I overlooked the divisibility argument and I'll try implementing the code with reduced iterations as an exercise.

Oh, awesome! I've been annoyed with the time.sleep(5) for a while now, I should have thought of this, thanks!

5. Jan 25, 2012

### Staff: Mentor

Code (Text):
if j == 0:
print(str(x) + ' is not a prime.')
time.sleep(5)
break
elif j != 0:
That test for j != 0 seems redundant.