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

Python preliminary numbers calculations: Here, we are going to contrast various calculations with figure prime numbers upto n term in python.

There are different techniques through which we can figure prime numbers up to n.

1) General Method:

In this strategy, we, as a rule, run two for circles in which the First one is utilized to build the number and the subsequent one is utilized to check whether the number is prime or not. Second circle runs from 2 to ( n/2 + 1 ) ( for better execution).

Note: This is the least productive technique (one ought not to utilize this if proficiency is required.)

2) Square-Root Method:

In this strategy, two circles run initial one is to build the number and the subsequent one is to check whether the number is prime or not. The subsequent circle runs from 2 to square root (number) (a number which is to be check), that is the reason the run length of a second for a circle is moderately little, that is the reason it’s proficient than the gullible methodology.

3) Sieve of Eratosthenes:

This is the best and most effective technique to figure the prime numbers up to n.

The calculation for Sieve of Eratosthenes:

Toward the finish of both the for circles, every one of the qualities that are set apart as TRUE is primes and all the composite numbers are set apart as FALSE in stage 3.

Time multifaceted nature : O(n*log(log(n)))

Note: Performance of General Method and SquareRoot Method can be expanded a smidgen on the off chance that we check just ODD numbers on the grounds that rather than 2 no significantly 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