1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python program to verify primes

  1. Jan 23, 2012 #1
    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. jcsd
  3. Jan 24, 2012 #2
    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. (:
     
  4. Jan 24, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    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
  5. Jan 25, 2012 #4
    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!
     
  6. Jan 25, 2012 #5

    NascentOxygen

    User Avatar

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Python program to verify primes
Loading...