Sieve of Eratosthenes (find prime numbers smaller than N)

Given a number (n), find all the prime numbers smaller than or equal to n.

 Sieve of Eratosthenes is one of the most efficient algorithms to find all prime numbers smaller than or equal to n. when n is smaller than 10 million or so.

 A prime number is a number divisible only by itself and one.
Example 13, 17, 7, etc.

Algorithm:

We use a boolean array which has a size of N i.e. arr[1...n].

We start from 2 and make the array value false for all the indexes which are multiples of 2.
credits: GeeksForGeeks

We find the next element in the array which is True. This is our next prime number i.e. 3.
We make the array value false for all the indexes which are multiples of 3.
credits: GeeksForGeeks
And then again find the next True value which is the next prime number.
We repeat this process until we reach n.

At the end, all the values in the array which are True have a prime index value.

Optimization:

Rather than running the loop for prime p from (2*p to n) we can start making values False from p*p = (p2 to n) as all the values from (2*p to p2) will actually be made False already by previous prime numbers because of the property that all numbers are product of two or more prime numbers.

Code in Python:

# Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
""" The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is
smaller than 10 million or so """


# function to find prime numbers less than or equal to num
def find_primes_sieve(num):
    # list of all numbers upto n
    intList = [True for i in range(num+1)]

    # first prime
    p = 2

    while p * p <= num:

        # if intList[p] is True means its a prime number
        if intList[p]:
            for i in range(p**2, num+1, p):
                intList[i] = False

        p += 1

    lis = []
    for i in range(2, len(intList)):
        if intList[i]:
            lis.append(i)

    return lis


primes = find_primes_sieve(30)
print(primes)
"""
Outputs:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
"""

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal

Comments

Post a Comment

Popular posts from this blog

Sorted Array: Binary Search

Image
Binary Search: Binary search is useful when the input array elements are sorted. The algorithm divides the search space into half each time the element to be searched (x) is not found. It uses 3 conditions: 1. If the current element of the array is equal to x, then return the index. 2. Else if the current element of the array is less than x, then x will be present towards the right of the current element (because the array is sorted). 3. Else if the current element of the array is greater than x, then x will be present towards the left of the current element. GeeksForGeeks: Binary Search Example Code in Python 3: # Function for binary search # inputs: sorted array 'arr', key to be searched 'x' # returns: index of the occurrence of x found in arr def binary_search(arr, x): l = 0 r = len(arr) # while the left index marker < right index marker while l < r: # find the index of the middle element mid = int(l + ((r - l...
Keep reading

Segregate Even Odd value nodes in a linked list

Image
Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to ...
Keep reading

What is 3 Algorithms Per Week?

Image
What are Algorithms? Google gives us the first result as below when we search the term "Algorithm": Surely I didn’t understand what it really meant the first time I read this, and yet it is a very important part of our lives, especially for the developers. Name any company in the IT sector, from Google, Microsoft, Facebook to Infosys and TCS, every one of them asks questions based on algorithms and data structures in their interviews. Algorithm is nothing but logic or steps to solve a given problem. Be it sorting of numbers in non increasing order or finding the shortest path from your home to your college on Google Maps, algorithms are everywhere. Why know about Data Structures and Algorithms (DSA)? So, why do these tech companies emphasise on learning DSA? In todays fast paced and every growing world speed and space are very important. We want speed to get our google search results quickly, get faster to the destination location and we want space ...
Keep reading