Home » Python » Python Programs

Python program to count prime numbers up to N (Different Methods)

Python | Count Prime Numbers: Here, we will learn how to count the total number of prime numbers up to N using different methods in Python? By Sanjeev Last updated : April 14, 2023

Different Methods to Count Prime Numbers up to N

1. General Method

In this method, we usually run two for loops in which the First one is used to increase the number and the second one is used to check whether the number is prime or not. Second loop runs from 2 to ( n / 2 + 1 ) ( for better performance).

Note: This is the least efficient method (one should not use this if efficiency is required.)

2. Square-Root Method

In this method, two loops run first one is to increase the number and the second one is to check whether the number is prime or not. The second loop runs from 2 to square root (number) (a number which is to be check), that’s why the run length of second for loop is relatively small, that’s why it’s efficient than the naïve approach.

3. Sieve of Eratosthenes

This is the best and most efficient method to calculate the prime numbers upto n.

Algorithm for Sieve of Eratosthenes:

Let A be an array from 2 to n.
Set all the values to True (we are considering every number to be Prime)
For loop from p == 2 (smallest prime number)
For loop from p² to n
Mark all the multiples of p as False and increase the value of p to the next prime number
End of second FOR loop
End of first FOR loop

At the end of both the for loops, all the values that are marked as TRUE are primes and all the composite numbers are marked as FALSE in step 3.

Time complexity : O(n*log(log(n)))

Note: Performance of General Method and SquareRoot Method can be increased a little bit if we check only ODD numbers because instead of 2 no even number is prime.

Python program to count prime numbers up to N

from time import time
from math import sqrt

def general_approach(n):
    '''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    '''
    start = time()
    count = 0
    for i in range(2, n):
        flag = 0
        x = i // 2 + 1
        for j in range(2, x):
            if i % j == 0:
                flag = 1
                break
        if flag == 0:
            count += 1
    stop = time()
    print("Count =", count, "Elapsed time:", stop - start, "seconds")

def count_primes_by_sqrt_method(n):
    '''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    '''
    start = time()
    count = 0
    for val in range(2, n):
        root = round(sqrt(val)) + 1
        for trial_factor in range(2, root):
            if val % trial_factor == 0:
                break
        else:
            count += 1
    stop = time()
    print("Count =", count, "Elapsed time:", stop - start, "seconds")

def seive(n):
    '''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    Algorithm originally developed by Eratosthenes.
    '''
    start = time()
    # Each position in the Boolean list indicates
    # if the number of that position is not prime:
    # false means "prime," and true means "composite."
    # Initially all numbers are prime until proven otherwise
    nonprimes = n * [False]
    count = 0
    nonprimes[0] = nonprimes[1] = True
    for i in range(2, n):
        if not nonprimes[i]:
            count += 1
            for j in range(2*i, n, i):
                nonprimes[j] = True
    stop = time()
    print("Count =", count, "Elapsed time:", stop - start, "seconds")

    # Time complexity : O(n*log(log(n)))

def main():
    print("For N == 200000\n")
    print('Sieve of Eratosthenes Method')
    seive(200000)
    print('\nSquare Root Method')
    count_primes_by_sqrt_method(200000)
    print('\nGeneral Approach')
    general_approach(200000)

main()

Output

For N == 200000

Sieve of Eratosthenes Method
Count = 17984 Elapsed time: 0.050385475158691406 seconds

Square Root Method
Count = 17984 Elapsed time: 0.9392056465148926 seconds

General Approach
Count = 17984 Elapsed time: 101.83296346664429 seconds