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().