Python program to calculate prime numbers (using different algorithms) upto n

Algorithm for Sieve of Eratosthenes:

1. Let A be an array from 2 to n.
   Set all the values to True (we are considering every number to be Prime)
2. For loop from p == 2 (smallest prime number)
3. For loop from p2 to n
   Mark all the multiples of p as False and increase the value of p to the next prime number
4. End of second FOR loop
5. 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.

Example:

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