Prime or not?

Question

How would I go about creating a code that can determine whether a number is prime or not? I am at a loss as to how to even begin this code. (I’m new to python.)

Answer 1

When's a number `n` prime?
When `n` has no other factors than 1 and itself.

What's a factor of `n`?
A number that divides `n` evenly.

When does a number `i` divide `n` evenly?
We divide `n/i` and see if there's a remainder left over. We are looking for a remainder of 0.

For example:
16/3 = 5, with a remainder of 1. So 3 is not a factor of 16.
15/3 = 5, with remainder 0. So 3 is a factor of 15.

Python can tell us the remainder of a division problem, by what's called the modulo operator:
16%3 == 1
15%3 == 0

So your task is to check all the numbers from `2` to `n-1` and make sure that none of them divide your number `n`.
As soon as you encounter a number with modulus > 0 you can stop and you know it's not a prime number.

That should be solvable with a for loop!

(PS: You don't really need to check all the numbers up to n-1. n/2 will work too, or even √n rounded down, for maths reasons. Just in case you want to speed up your program.)

Answer 2

Schindlabua I wasnt expecting such a detailed and explanatory answer! This really helps, thank you :)