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

Reverse alternate k nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self
Keep reading

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

Tree data structure

Image
Tree Data structure Till now we have seen linear data structures such as arrays and linked lists. In these data structures, we had only one child following the previous parent. 5 is parent of 7 7 is parent of 3 3 is parent of 4 Tree are hierarchical data structures. Here each node can have multiple children. A popular implementation of Tree is a Binary tree where each node has at most 2 children (known as the left child and right child). The top most node is known as the root of the tree similar to the head node in a linked list.  The node directly above some node is called its parent. Application: Trees can are used in various applications that we see every day.  For example, the directory structure that we see in our operating systems (file explorer in Windows, finder in MacOS) is a great example of using tree where each folder is a node and each sub folder are its children, the files can be considered as leaf nodes i.e. the bottom most nodes in the tree whic
Keep reading