What is the process to find if a number is prime?

Question

I know this has been asked before, but I'm trying to learn Python and I don't want the answer handed to me in the form of completed code. I'm hoping someone can just point me in the right direction.

I know how to do loops and functions and stuff, but I don't know how I should set up a check to determine if a number is prime or not. This might actually be a simple math question really.

What math process do I use to find out if a number is a prime?

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

Pseudo-code

Here's how it could be broken down:

First, you'll need to ask the user to input a number and store that number in a variable, say num_to_test
Check that it is valid, i.e. it is an integer larger than 2
Then, for each number d between 2 and num_to_test-1, we will try and figure out if d divides num_to_test
If we find one that does, we can break the loop ! There exists an integer that is not 1 and not our number, and that divides our number. Thus num_to_test is not a prime.
If we reach the end of the loop and have found nothing, then our number is a prime.
Finally, tell the user about the result and you're done.

Now, how to do this pythonically?

User input

With Python 3, all you have to do to request an integer input is a line like this:

num_to_test = int(input('What\'s your number?'))

Of course, you want to be sure that the user enters a number, that's why you'll surround this by a try/except block and a while True loop, asking again and again until the answer is valid.

while True:
    try:
        # request input
        if satisfies_your_conditions(num):
            break
        else:
            # explain why not good
    except ValueError:
        # print error message

Looping over the integers

First thing to know, you don't need to go further than the square root of num_to_test.

sr = int(math.sqrt(num_to_test))+1

And you'll do the test for d in range(2, sr). Since we don't have a list of previously verified primes, we'll have to do it for all integers. To check whether d divides num_to_test, use the modulo operation:

if num_to_test % d == 0:
    # d does divide num_to_test
else:
    # d does not divide num_to_test

Ending

One cool feature is the for...else...:

for ... :
    # do your tests, with possibility of breaking the loop
else:
    # this part of the code will only be reached if the loop did not break

With this, you'll be able to set a boolean to True or False and then print the result to the user

You could use the ternary operator for this:

print('some string' if is_prime else 'another string')

Code proposition

This is only a possibility of implementation among others.

import math

def main():
    while True:
        try:
            num_to_test = int(input('What\'s your number?   '))
            if num_to_test == int(num_to_test) and num_to_test > 2:
                break
            else:
                print('Must be an integer larger than 1. Try again.')
        except (NameError, ValueError):
            print('Not a number. Try again.')

    sr = int(math.sqrt(num_to_test))+1
    for d in range(2, sr):
        if num_to_test % d == 0:
            is_prime = False
            break
    else:
        is_prime = True

    print('%d is a prime number'%num_to_test if is_prime else '%d is not prime'%num_to_test)

if __name__ == '__main__':
    main()

What is the process to find if a number is prime?

Pseudo-code

Code proposition

Sign up