Josh - 1 year ago 67
Python Question

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

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?

# 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()
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download