Q:

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

belongs to collection: Python basic programs

mahmoud2506
Save to bookmark
|
2022-05-18
|
  230 
0

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.

Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-18
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Python basic programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Python program for not None test... >>
<< Python program to check prime number...