A Beginner’s Guide to Find the Number of Prime Numbers with Python

Problem Statement:

Problem: Write a function count_prime(nums) that takes an integer nums as input and returns the count of prime numbers up to and including nums. Additionally, the function should print out the list of prime numbers found within this range.

Example: Suppose we call the function with nums = 10. The expected output would be:

The list of prime numbers is: [2, 3, 5, 7]

The number of prime numbers is: 4

What is Prime Number ?

Approach: Let’s break down the problem into smaller steps:

1. Generate a list of numbers: Create a list of integers from 2 up to nums.

2. Check for primality: For each number in the list, determine if it is prime.

3. Count and store prime numbers: Keep track of the prime numbers found.

4. Print the results: Display the list of prime numbers and their count.

Writing the Python Function

#Efficient way of writing code to find the Prime Numbers.
def is_prime(num):
    #Check if a number is prime.
    if num < 2:
        return False
    for divisor in range(2, int(num**0.5) + 1):
        if num % divisor == 0:
            return False
    return True

def count_prime(nums):
    #Count prime numbers up to and including nums.
    prime_list = []
    for num in range(2, nums + 1):
        if is_prime(num):
            prime_list.append(num)
    print(f"The list of prime numbers is: {prime_list}")
    return len(prime_list)

Explanation:

1. The is_prime(num) function checks if a given number is prime by iterating through potential divisors up to the square root of the number.

2. The count_prime(nums) function generates a list of prime numbers up to nums and prints the list along with the count.

Another Method to write a code for the same problem statement, but that is not efficient.

def is_prime(num):
# Check if a number is prime.
    if num < 2:
        return False
    for divisor in range(2,num):
        if num % divisor == 0:
            return False
    return True

def count_prime(nums):
#     Count prime numbers up to and including nums.
    prime_list = []
    for num in range(2, nums + 1):
        if is_prime(num):
            prime_list.append(num)
    print(f"The list of prime numbers is: {prime_list}")
    return len(prime_list)

Above code is correct and will successfully count the number of prime numbers up to and including a given number. However, it can be optimized. The function is_prime(num) checks divisibility up to num, but we only need to check up to the square root of num because a larger factor of the number would be a multiple of a smaller factor that has already been checked.

Problem Statement:

Write a python program to print the numbers in the given range.

Note : for range take input from User.

# Inefficient code:
start = int(input("Enter the Starting Range: "))

while start<=1:
    print("Please Enter the Starting Limit greater than 1.")
    start = int(input("Enter the Starting Range: "))

else:    
    end = int(input("Enter the Ending Range: "))

    for n in range(start, end+1):
        prime = True
        for d in range(2, n):
            if n%d == 0:
                prime = False
                break

        if prime == True:
            print(n , end=' ')

Above code is not efficient to find the list of prime numbers. we can prepare the efficient program, by not checking from 2 to n.

Currently, our inner loop checks all numbers from 2 up to n-1 to determine if n is prime. we can reduce the number of iterations by checking up to the square root of n, because a larger factor would have a corresponding smaller factor that would have been identified already.

#Efficient code:
start = int(input("Enter the Starting Range: "))

while start<=1:
    print("Please Enter the Starting Limit greater than 1.")
    start = int(input("Enter the Starting Range: "))

#else condition not required because once you're out off the loop it execute next step.
#no need of while

end = int(input("Enter the Ending Range: "))

# we can prepare the efficient program, by not checking from 2 to n.

for n in range(start, end+1):
    prime = True
    temp = int(n**0.5)    

# Currently, your inner loop checks all numbers from 2 up to n-1 to determine if n is prime. 
#You can reduce the number of iterations by checking up to the square root of n, because a larger factor would have a corresponding smaller factor that would have been identified already.

    for d in range(2, temp+1):
        if n%d == 0:
            prime = False
            break

    if prime == True:
        print(n , end= ' ')

We can write above program in more efficient way.

• Prime List: The program maintains a list of prime numbers (primes) and only checks divisibility against these numbers. This is because if a number n is not a prime, it must have a prime factor.

• Early Termination: The loop breaks as soon as it finds a factor of n, which means it doesn’t perform unnecessary checks once it’s determined that n is not prime.

• Checking Only Odd Numbers: The program checks only odd numbers (since even numbers can’t be prime), which effectively reduces the search space by half.

    def count_primes2(num):
        primes = [2]
        x = 3
        if num < 2:
            return 0
        while x <= num:
            for y in primes:  # use the primes list!
                if x%y == 0:
                    x += 2
                    break
            else:
                primes.append(x)
                x = x + 2  # only check odd number as Even Number can't be prime.
  
        print(primes, end=' ')
  

I hope this blog will help you to write efficient code for prime number. Always try to write efficient code as much as possible.

All the best👍.

Keep Learning, Keep Practicing, Keep Rocking🤘.

---