A prime number is a number greater than 1 that can be divided only by 1 and itself. For example, 2, 3, 5, 7 and 29 are prime. 1 is not prime, and 2 is the only even prime number. In this lesson you will write a Python program that checks whether a number is prime, and then use it to list all primes up to 50.

Run the code in our online Python compiler. The compiler does not take keyboard input, so the examples use fixed values.

 

The logic

  1. If the number is less than 2, it is not prime.
  2. Try dividing the number by every value from 2 up to its square root.
  3. If any value divides it exactly (the remainder is 0), the number is not prime.
  4. If none of them divides it, the number is prime.

We only need to check up to the square root because factors come in pairs. If a number has a factor larger than its square root, it also has a matching factor smaller than the square root, which we would already have found.

 

Program: check one number

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

for number in [29, 1, 2, 15, 97, 100]:
    print(number, is_prime(number))

Output:

29 True
1 False
2 True
15 False
97 True
100 False

How it works

Take n = 29. Its square root is about 5.38, so the loop checks 2, 3, 4 and 5. None of them divides 29 exactly, so the function returns True.

Take n = 15. The square root is about 3.87, so the loop checks 2 and 3. Since 15 % 3 is 0, the function returns False straight away.

The expression n % i gives the remainder of dividing n by i. A remainder of 0 means i divides n exactly.

 

Program: print all primes up to 50

Add this below the is_prime() function:

primes = [n for n in range(2, 51) if is_prime(n)]
print(primes)

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Take the number from the user (on your computer)

On your own computer, you can read the number from the keyboard:

number = int(input('Enter a number: '))
if is_prime(number):
    print(number, 'is a prime number')
else:
    print(number, 'is not a prime number')

Our online compiler does not support input() yet, so use a fixed value there.

 

Common mistakes

  • Treating 1 as prime. 1 is not prime, so the check n < 2 is needed.
  • Checking every number up to n. It gives the right answer but is much slower than stopping at the square root.
  • Forgetting that 2 is prime. The loop for n = 2 does not run, so the function returns True, which is correct.

 

Practice questions

  1. Write a program that prints all prime numbers between 100 and 150.
  2. Count how many prime numbers there are below 100.
  3. Write a function that returns the first prime number greater than a given number.
  4. Print the prime factors of 84.

 

FAQs

Is 1 a prime number?

No. A prime number must be greater than 1.

Why do we check only up to the square root?

Factors come in pairs, so if a number has a factor above its square root, it also has one below it. Checking up to the square root is enough.

Is 2 a prime number?

Yes. It is the smallest prime and the only even prime.

PreviousNext