Skip to main content

Sieve of Eratosthenes


The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It was devised by the Greek mathematician Eratosthenes around 200 BCE, and it is still used today in various applications, such as cryptography and computer science.

The basic idea of the Sieve of Eratosthenes is to eliminate all composite numbers (i.e., non-prime numbers) in a range of numbers from 2 to some upper limit. To do this, we start by marking all the numbers from 2 to the limit as potential primes. We then iterate through the list of numbers, starting with 2, and for each prime number we encounter, we mark all its multiples as composite. This process is repeated for each subsequent prime number until we reach the end of the list.

At the end of this process, all the unmarked numbers that remain are primes. This is because any composite number in the list would have been marked as a multiple of some smaller prime number, and thus eliminated from the list. For example, if we start with the list [2, 3, 4, 5, 6, 7, 8, 9, 10] and apply the Sieve of Eratosthenes, we would mark 4, 6, 8, and 10 as composite (multiples of 2), and 9 as composite (a multiple of 3). The remaining unmarked numbers, 2, 3, 5, and 7, are all prime.

The Sieve of Eratosthenes has a time complexity of O(n log log n), which is very efficient for most practical purposes. However, for extremely large values of n, the algorithm can become impractical, as it requires an array of size n to store the potential primes. In these cases, more advanced algorithms such as the Sieve of Atkin or the AKS primality test may be used instead.

Overall, the Sieve of Eratosthenes is a simple and elegant algorithm for finding primes that has stood the test of time. Its basic principle of eliminating composite numbers through repeated iteration has inspired many other algorithms and mathematical discoveries over the centuries.


ALGORITHM :

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a given limit. The algorithm works by eliminating all composite numbers (i.e., non-prime numbers) in a range of numbers from 2 to some upper limit. Here are the steps to execute the algorithm:

  1. Create a list of all the numbers from 2 to the upper limit.
  2. Start with the first prime number, which is 2.
  3. Mark all the multiples of the current prime number as composite.
  4. Find the next prime number by selecting the smallest number in the list that is not yet marked as composite. This number is the next prime number.
  5. Repeat steps 3 and 4 until all the prime numbers up to the limit have been found.
  6. The unmarked numbers that remain in the list are all prime.

PSEUDO CODE :

Here's the pseudo code for the Sieve of Eratosthenes algorithm:

The algorithm takes an integer n as input and returns a list of all prime numbers up to n. The algorithm works by creating an array A of Boolean values, where each element A[i] indicates whether i is a prime number. Initially, all values of A are set to true. The algorithm then iterates through the array from 2 to the square root of n, checking whether each number is prime. If the number is prime, the algorithm marks all of its multiples as composite by setting their corresponding values in A to false. Finally, the algorithm outputs all values of i such that A[i] is true, which are the prime numbers up to n.

PYTHON CODE :

Here's an implementation of the Sieve of Eratosthenes algorithm in Python:

The function takes an integer n as input and returns a list of all prime numbers up to n. The algorithm works by creating a list of all numbers from 2 to n, and then iterating through the list, marking all multiples of each prime number as composite. The algorithm stops when it reaches the square root of n, since any composite number greater than the square root of n must have a factor less than the square root of n. Finally, the function collects all unmarked numbers into a list and returns it as the result.

JAVA CODE :

Here's an implementation of the Sieve of Eratosthenes algorithm in Java:


The sieveOfEratosthenes method takes an integer n as input and returns a list of all prime numbers up to n. The algorithm works by creating an array primes of Boolean values, where each element primes[i] indicates whether i is a prime number. Initially, all values of primes are set to true. The algorithm then iterates through the array from 2 to the square root of n, checking whether each number is prime. If the number is prime, the algorithm marks all of its multiples as composite by setting their corresponding values in primes to false. Finally, the algorithm collects all values of i such that primes[i] is true, which are the prime numbers up to n, and returns them as a list. The main method demonstrates how to use the sieveOfEratosthenes method to find prime numbers up to a given limit.

C CODE :

Here's an implementation of the Sieve of Eratosthenes algorithm in C:


In this implementation, we create a boolean array primes of size n+1, where primes[i] is initially set to 1 for all i. We then iterate over all prime numbers p from 2 up to the square root of n, and for each prime p, we mark all its multiples as non-prime by setting primes[i*p] to 0 for all i >= p*p and i <= n. Finally, we print out all numbers p such that primes[p] is still 1, which correspond to the prime numbers up to n.

C++ CODE :

Here's an implementation of the Sieve of Eratosthenes algorithm in C++:


In this implementation, we create a boolean vector primes of size n+1, where primes[i] is initially set to true for all i. We then iterate over all prime numbers p from 2 up to the square root of n, and for each prime p, we mark all its multiples as non-prime by setting primes[i*p] to false for all i >= p*p and i <= n. Finally, we print out all numbers p such that primes[p] is still true, which correspond to the prime numbers up to n.

JAVASCRIPT CODE :

Here's an implementation of the Sieve of Eratosthenes algorithm in JavaScript:


In this implementation, we create an array primes of boolean values of size n+1, where primes[i] is initially set to true for all i. We then iterate over all prime numbers p from 2 up to the square root of n, and for each prime p, we mark all its multiples as non-prime by setting primes[i*p] to false for all i >= p*p and i <= n. Finally, we create an array result of prime numbers up to n by adding all numbers p such that primes[p] is still true. The function sieve() returns this array.

In the example usage, we call sieve(n) with n = 50, and store the result in the variable primes. We then print out the result using console.log().

Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more