Python Python program to verify primes

[llstelle]

Homework Statement

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...

#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

 

[llstelle]

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

#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. (:

 

[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.

 

[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.

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.

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

 

[NascentOxygen]

        if j == 0:
            print(str(x) + ' is not a prime.')
            time.sleep(5)
            break
        elif j != 0:

That test for j != 0 seems redundant.