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:*

- 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
^{2}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.

**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions