How to find all the prime numbers within a given range?

This is a question that is asked very often in programming assignments and also in coding tests during interviews. We will try and solve this problem using Python Code. We will also try and optimize the code.

First of all let us define what a Prime Number is. A Prime Number is a number that has only 2 divisors namely 1 and itself. The reverse definition would be " A Prime Number is a number that is divisible by at least 1 number other than 1 and itself. The second definition is the one that we will use.

How do we know if a number is divisible by another number?

You try divide the number by a divisor and check the remainder. If the remainder is 0 then the number is divisible.

33 divided by 10 gives a remainder of 3 so not divisible.

33 divided by 11 gives a remainder of 0 so it is divisible.

The remainder operator or as it is more commonly called the modulus operator in most languages is %.

33 % 10 is 3, and 33 % 11 is 0 in Python

Now, we know every single number is divisible by 1, and itself. So, we will start checking the divisibility from 2. What should be the upper limit?

Let us try and find out the factors of some numbers and attempt to find out a pattern.

What are the factors of the number 36?

We start from 2 because 1 divides everything so we need not check it.

2 X 18

3 X 12

4 X 9

6 X 6

9 X 4

12 x 3

18 X 2.

The factors are repeated in the reverse order after 6 X 6. Does this always happen?
Let us try with another number 60.

2 X 30

3 X 20

4 X 15

5 X 12

6 X 10

10 X 6

12 x 5

15 X 4

20 X 3

30 X 2

The factors are being repeated once again after 6 X 10. In case of 36 they repeated after 6 X 6.

Factors are repeated after the square root. 6 is the square root of 36 and the square root of 60 will lie between 6 and 10. What does this mean? This means that a number not divided till its square root cannot be divided afterwards. So, we need to check up to its square root only.

Let us develop a program to check if a given number is prime now.

Program to check if a number is prime.

# Program to check if a number is prime


n = 37  # Number that is to be checked whether it is prime or not
limit = int(n ** 0.5)  # Square root of n is the limit to which it is to be checked
for i in range(2, limit + 1):  # Loop to the square root
    if n % i == 0:  # Check for remainder =0
        print(n, " is not prime")  # Number isn't prime
        exit(0)  # end the program

print(n, " is prime")  # Program didn't end in loop so the number is prime

# End program

Here is the output of the program when run with n=37


37  is prime

Process finished with exit code 0

With n=39, we get


39  is not prime

Process finished with exit code 0

We will modify this program to find prime numbers to a given limit now.

We need to create loop that generates n from 2 to our given limit and check for it being prime using our current logic and then print it if it is prime.

Program to find all prime numbers up to a limit

# Program to find all prime numbers up to a limit


primeLimit = 10  # Find prime numbers to this limit
count = 0  # Variable where the count of primes found will be stored
primes = []  # List in which primes will be stored
for n in range(2, primeLimit + 1):  # Run a loop from 2 to the required limit
    limit = int(n ** 0.5)  # Limit to which divisors need to be checked
    isPrime = True  # Assume the number to be prime
    for divisor in range(2, limit + 1):  # Run a loop to the limit
        if n % divisor == 0:  # Check whether the remainder upon division is 0
            isPrime = False  # If remainder is 0 then the number isn't prime
            break  # If it isn't prime then break the loop
    if isPrime:
        print(n, end=",")
        count += 1  # Prime found. Increment the count
print("\nPrimes Count=", count)

# End program

Sample run with primeLimit = 10


2,3,5,7,
Primes Count= 4

Process finished with exit code 0

Sample run with primeLimit=100


2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
Primes Count= 25

Process finished with exit code 0

What is the time complexity of this program. Let us try and find out the number of times the inner divisor loop runs.

Program to find primes up to a limit and also count the number of times the loop runs.

# Program to find all prime numbers up to a limit


primeLimit = 100  # Find prime numbers to this limit
innerLoopRuns = 0  # Count the runs of the inner loop
count = 0  # Variable where the count of primes found will be stored
primes = []  # List in which primes will be stored
for n in range(2, primeLimit + 1):  # Run a loop from 2 to the required limit
    limit = int(n ** 0.5)  # Limit to which divisors need to be checked
    isPrime = True  # Assume the number to be prime
    for divisor in range(2, limit + 1):  # Run a loop to the limit
        innerLoopRuns += 1
        if n % divisor == 0:  # Check whether the remainder upon division is 0
            isPrime = False  # If remainder is 0 then the number isn't prime
            break  # If it isn't prime then break the loop
    if isPrime:
        print(n, end=",")
        count += 1  # Prime found. Increment the count
print("\nPrimes Count=", count)
print("\nInner loop runs is ",innerLoopRuns)

# End program

Output


2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
Primes Count= 25

Inner loop runs is  236

Process finished with exit code 0

The number of times the loop runs is 236.

Can, we reduce this? There are no even prime numbers other than 2, so let us stop searching for even numbers other than 2.

Optimized version of the above program.

# Program to find all prime numbers up to a limit


primeLimit = 100  # Find prime numbers to this limit
innerLoopRuns = 0  # Count the runs of the inner loop
count = 0  # Variable where the count of primes found will be stored
primes = []  # List in which primes will be stored
print("2,")  # 2 is a prime number. Print it
count += 1  # Increment prime count by 1
for n in range(3, primeLimit + 1,2):  # Run a loop from 2 to the required limit. Start at 3 and increment by 2. Odd numbers only
    limit = int(n ** 0.5)  # Limit to which divisors need to be checked
    isPrime = True  # Assume the number to be prime
    for divisor in range(2, limit + 1):  # Run a loop to the limit
        innerLoopRuns += 1
        if n % divisor == 0:  # Check whether the remainder upon division is 0
            isPrime = False  # If remainder is 0 then the number isn't prime
            break  # If it isn't prime then break the loop
    if isPrime:
        print(n, end=",")
        count += 1  # Prime found. Increment the count
print("\nPrimes Count=", count)
print("\nInner loop runs is ", innerLoopRuns)

# End program

Output


2,
3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
Primes Count= 25

Inner loop runs is  187

Process finished with exit code 0

We have managed to reduce the no of runs from 236 to 187 now. can we reduce it further. The divisor inner loop can be made an odd number loop as well.

Program optimized further

# Program to find all prime numbers up to a limit


primeLimit = 100  # Find prime numbers to this limit
innerLoopRuns = 0  # Count the runs of the inner loop
count = 0  # Variable where the count of primes found will be stored
primes = []  # List in which primes will be stored
print("2,")  # 2 is a prime number. Print it
count += 1  # Increment prime count by 1
for n in range(3, primeLimit + 1,
               2):  # Run a loop from 2 to the required limit. Start at 3 and increment by 2. Odd numbers only
    limit = int(n ** 0.5)  # Limit to which divisors need to be checked
    isPrime = True  # Assume the number to be prime
    for divisor in range(3, limit + 1, 2):  # Run a loop to the limit
        innerLoopRuns += 1
        if n % divisor == 0:  # Check whether the remainder upon division is 0
            isPrime = False  # If remainder is 0 then the number isn't prime
            break  # If it isn't prime then break the loop
    if isPrime:
        print(n, end=",")
        count += 1  # Prime found. Increment the count
print("\nPrimes Count=", count)
print("\nInner loop runs is ", innerLoopRuns)

# End program

Output


2,
3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
Primes Count= 25

Inner loop runs is  87

Process finished with exit code 0

Consider the following series.

2,3,5,7,11,13,17,19,23,25,29,31,35,37.

Examine this starting at 5.

2,3,
5 + 2=7,
7+4=11,
11+2=13,
13+4=17,
17+2=19,
19+4=23,
23+2=25,
25+4=29

Increase by 2, then 4, then 2 and 4 and so on. This will not give a prime number always but if you get a prime number then it will be from this series only. How to generate this series.
Take a variable t for instance and set it to 2,
t=2,
then set t= 6-t=4
again t= 6-t=2, and so on,,,

Sample program

# Program to generate a 2,4,2,4,2,4 series

t = 2
for i in range(10):
    print(t, end=",")
    t = 6 - t

# End program

Output


2,4,2,4,2,4,2,4,2,4,
Process finished with exit code 0

Program after adding these innovations.

# Program to find all prime numbers up to a limit


primeLimit = 100  # Find prime numbers to this limit
innerLoopRuns = 0  # Count the runs of the inner loop
count = 0  # Variable where the count of primes found will be stored
primes = []  # List in which primes will be stored
print("2,3,", end="")  # 2 and 3 are prime numbers. Print it
count += 2  # Increment prime count by 2
t1 = 2
for n in range(5, primeLimit + 1,
               t1):  # Run a loop from 2 to the required limit. Start at 3 and increment by 2. Odd numbers only
    t1 = 6 - t1
    if n % 3 == 0:  # Check for division by 3 and go back and generate another number if divisible by 3
        continue
    limit = int(n ** 0.5)  # Limit to which divisors need to be checked
    isPrime = True  # Assume the number to be prime
    t2 = 2
    for divisor in range(5, limit + 1, t2):  # Run a loop to the limit
        t2 = 6 - t2
        innerLoopRuns += 1
        if n % divisor == 0:  # Check whether the remainder upon division is 0
            isPrime = False  # If remainder is 0 then the number isn't prime
            break  # If it isn't prime then break the loop
    if isPrime:
        print(n, end=",")
        count += 1  # Prime found. Increment the count
print("\nPrimes Count=", count)
print("\nInner loop runs is ", innerLoopRuns)

# End program

Output


2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
Primes Count= 25

Inner loop runs is  41

Process finished with exit code 0

Program run with primeLimit=500


2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
Primes Count= 95

Inner loop runs is  661

Process finished with exit code 0