Sign in Subscribe
python

Today's learning: Simple Python Skills -- Is a number prime?

DanielxBlack

• 8 min read

I enjoy scripting, but I just haven't had the time to dedicate to improving my skillset. I know, that's just an excuse, but if I'm not at work, I'm studying up for my OSCP, or learning about web apps. I wish I could make more time in the day, but I have to work with what I have and try to make the best of my free hours.

I'm thinking the occassional simple Python script to help me learn programming logic will do the trick.

I'll admit, I cheated a bit to figure this one out, but it's a fairly basic coding problem I think we've all encountered in workbooks and training courses. We want to take an input and determine whether or not it's a prime number.

First, what is a prime number?

This is probably embarassing for anyone to admit, but after maybe ... I dunno, 7th grade math, you just kind of don't keep in mind what a prime number is or what a composite number is.

A prime number is a number that is divisible by only 1 and itself. For instance, 3 is a prime number. The number 4 is a composite number. What exactly does that mean?

Only one pair of numbers can multiply to make 3. Those two numbers are 1 and 3. Same with 13. Only 1 and 13 can multiply to make 13. In other words, the factors of 3 are "1" and "3." The factors of 13 are "1" and "13."

Composite numbers are different. Let's take 4, for example.

  • 1x4
  • 2x2

See that? 1 x 4 is 4, and so is 2 x 2. This means that the factors of 4 are 1,2 and 4.

Another composite number is 6:

  • 1x6
  • 2x3

This means that the factors of 6 are 1,2,3 and 6.

Knowing that, how do we find a prime?

We can determine that a number is a prime, according to factmonster, by dividing by 2 (2 is the only even number that is a prime, so it's the exception). If you get a whole number, it cannot be a prime. For instance, divide 12 by 2, and I get 6. This means 6 is a factor of 12. It cannot be a prime number.

If you divide by 2 and you do not have a whole number, you will try dividing it by prime numbers, such as 3,5, etc. until you reach the number you are trying to determine is prime. If any of those turns out to be a whole number, the number is not prime. For instance, 9.

  • 9/2 = 4.5

We did not get a whole number. It might be a prime number. Next, we divide by 3:

  • 9/3 = 3

We got a whole number. This means nine is not a prime number. Its factors are 1,3 and 9.

The modulo function in Python

The modulo function %, returns the remainder of a number. For instance, the following Python snippet:

9%3
0
9%2
1
9%6
3
  • 9/3 has a remainder of 0.
  • 9/2 has a remainder of 1.
  • 9/6 has a remainder of 3.

We know that 9 is not a prime number.

Where does Python fit in here?

So, we know what a prime number is. We know how to find it. Basically, what we are trying to do is determine if a number is prime by doing the following; let's pretend our number is 13:

# We start with two, because num % 1 will *always* be 0.
>>> 13%2  
1
>>> 13%2
1
>>> 13%3
1
>>> 13%4
1
>>> 13%5
3
>>> 13%6
1
>>> 13%7
6
>>> 13%8
5
>>> 13%9
4
>>> 13%10
3
>>> 13%11
2
>>> 13%12
1
# we also don't worry about 13%13
# because the number % itself will *always* be 0

See what happened here? We took each number between 1 and 13 (2-12) and divided them, then checked the remainder (with modulo). If the number was anything other than 0, this tells us that the 13 is not divisible by whatever we are dividing it by, because we have a remainder. Make sense?

However, if we take 4:

>>> 4%2
0

We immediately get a 0. This means that 4 is divisible by 2. It is not a prime number.

Let's try something that's going to make us iterate through a few more numbers:

>>> 9%2
1
>>> 9%3
0

We see that 9 modulo 2 is 1. Oooh! Maybe it's not a prime number!

Nope. 9 modulo 3 is 0. This means 9 is divisible by 3. We don't have a prime number afterall.

Our next step is to Pythonize this.

Making it into a script

I had to look at a guide to help myself kind of figure out how this works. That's what got me started writing this blog post. I, embarringly, realized that I really hadn't stopped to think about basic math in quite a few years. I'm sharing this with you, my reader (Sup, Brennon! [And anyone else who may have accidentally stumbled onto my blog]) because sometimes facts like these are hard to face – I've forgotten a ton of my grade school-level math.

My first challenge was to figure out: "Okay. It's been a hot minute, WTF is a prime number?"

After that, it was "Okay. HTF do I ask Python to do that?"

Finally, it was: "Hmm. Okay, let me spell this out for myself, so I can make sure I understand it, and I can explain it to someone else."

I kind of used this code as my starting point. I had to modify it slightly, because running "2" against it kinda broke the script by not returning anything. At least that's what happened when I tried it. Here's my code along with comments explaining almost every. single. line.

Check it:



# We will first create our function.
def isPrime():
    # This will take an input using input(), and assign a variable of "num".
    # Furthermore, it will convert the input to an integer with int()
    num = int(input("Give me a number: "))
    # if the number is higher than 1, we will test a range from 2 to the number we entered as our input.
    if num > 1:
        if num == 2:
            print("Two is a prime number.")
        # interate through each number in a range of 2 to our input number ...
        for i in range (2, num):
            # if our number modulo a number in range is equal to 0
            # in other words, if the number we enter is divided by a number between itself and 1,
            # and has a remainder of 0, we know that it is not a prime number.
            if (num % i) == 0:
                # This is not a prime number because the number we entered is evenly divisable by somehting between itself and 1
                print(f"The number {num} is not a prime number.")
                # Break, otherwise the code will print "num" number of times.
                break
            # if above condition is not met, the number will be a prime number.
            else:
                print(f"The number {num} is a prime number.")
                # Break. Otherwise, the line will print "num" number of times.
                break
    # if the number is less than 2, it's not a prime number.
    else:
        print(f"The number {num} is not a prime number")

# run our function.
isPrime()

What do we have here?

You can see that we create a function called isPrime:

# We will first create our function.
def isPrime():
    # This will take an input using input(), and assign a variable of "num".
    # Furthermore, it will convert the input to an integer with int()
    num = int(input("Give me a number: "))
    # if the number is higher than 1, we will test a range from 2 to the number we entered as our input.
    if num > 1:

The next line will take our input and convert it to an integer with a string requesting a number by prompting: "Give me a number: "

If the number is higher than 1, we will run the upcoming if statement. (Keep that if num > 1: piece in mind for later.)

Next line, we check it the number is 2:

        if num == 2:
            print("Two is a prime number.")

If the number is 2, we print "Two is a prime number." This is the slight modification I made since entering 2 seemed to break the code by not outputting anything. This part will make sense in the next chunk of code.

The next chunk of code:

# interate through each number in a range of 2 to our input number ...
        for i in range (2, num):
            # if our number modulo a number in range is equal to 0
            # in other words, if the number we enter is divided by a number between itself and 1,
            # and has a remainder of 0, we know that it is not a prime number.
            if (num % i) == 0:
                # This is not a prime number because the number we entered is evenly divisable by somehting between itself and 1
                print(f"The number {num} is not a prime number.")
                # Break, otherwise the code will print "num" number of times.
                break

Okay, what are we saying here? We are saying for every number (i) in a the range from 2 to the number. That is 2,3,4,5 ... until we reach the number right before the number we entered, we will test the modulo function and see if the remainder is 0. If we run into a factor with a remainder of 0, we inform the user that "num" is not a prime number and "break." Which tells the script to stop running.

We can also see why 2 didn't work. We never attempted 2%2 (which would have been 0). Furthermore, since the number was 2, we basically gave it no range. To my understanding, we told Python, "For every number above 2 and less than 2, give us the remainder." I don't know about you, but I'm not aware of many numbers that are more than 2 and less than 2 – or anywhere in-between.

Here are some examples. Let's print a range of 2-10 using ipython:

In [6]: for i in range (2,10):
   ...:     print(i)
   ...:
2
3
4
5
6
7
8
9

See that? It printed 2-9.

Now, let's try a range of 2-2, which is how Python would interpret our script if we entered a "2" as our "num" value:

In [7]: for i in range (2,2):
   ...:     print(i)
   ...:

We can see, it prints nothing. In other words, we would not be running 2% anything.

To fix that, we kind of eliminated that possibility by adding the statement that says: "If the user enters '2', don't bother. Just tell them 2 is a prime number, and close the program."

The next section:

            # if above condition is not met, the number will be a prime number.
            else:
                print(f"The number {num} is a prime number.")
                # Break. Otherwise, the line will print "num" number of times.
                break

If we have iterated through our entire range, and we never encountered an instance where the remainder was 0, the script continues to the "else" statement. It never found a zero so it will inform the user that the number "num" is a prime number. Then it breaks.

Finally:

    # if the number is less than 2, it's not a prime number.
    else:
        print(f"The number {num} is not a prime number")

# run our function.
isPrime()

If the number is less than 2, it's not a prime number.

That's it

Well, hopefully that kind of explains prime numbers and how to determine if a number is prime by using Python.

Bonus points

What happens if someone enters a letter? How do you adjust your script for that? Give it a shot. My old post on input validation and error handling may be helpful: https://danielxblack.ghost.io/remembering-input-validation-and-error-handling/

Sign up for more like this.

Enter your email
Subscribe