Home » Python » Python programs

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

Python primer numbers algorithms: Here, we are going to compare different algorithms to calculate prime numbers upto n term in python.
Submitted by Sanjeev, on April 02, 2019

There are various methods through which we can calculate prime numbers upto 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:

  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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.