Crafted to detect all prime numbers within a specified range or up to a given limit 'n', the algorithm is known as the Sieve of Eratosthenes. Named in honor of the ancient Greek mathematician Eratosthenes, this method provides a structured technique for filtering out non-prime numbers. Its significance lies in its utility for number theory and diverse computational scenarios.
The process starts by generating a sequence of numbers ranging from 2 to 'n' and initially considering all of them as prime. Subsequently, it methodically identifies and flags the multiples of every prime number, commencing with 2, the smallest prime. With each iteration, the algorithm gradually reveals the prime numbers present in the specified range.
The fundamental concept behind the Sieve of Eratosthenes lies in the fact that multiples of prime numbers are composite, not prime themselves. As a result, the method effectively sieves out non-prime numbers by iteratively identifying and marking these multiples. This iterative process persists until it reaches the square root of the given number 'n', at which point the unmarked numbers left are verified as prime.
Create a boolean array or vector with a length of 'n+1' to represent numbers from 0 to 'n'. Initially, all elements are assigned the value "true" to indicate that all numbers are considered prime.
Marking Composite Numbers: Begin with the initial prime number, denoted as 2. Indicate all products of 2 as composite by assigning their respective array elements to "false". This process excludes values such as 4, 6, 8, 10, and so forth, from the collection of potential prime integers.
Identify the Following Unchecked Value: Once multiples of 2 have been designated, locate the subsequent unchecked value exceeding 2. This specific value will represent the subsequent prime number, with 3 being the initial selection.
Repeat the Procedure: Proceed by flagging all multiples of the subsequent prime number (3 in this instance) as composite numbers. In the subsequent cycle, locate the subsequent unflagged numeral, which will represent the subsequent prime number (5 in this example), and replicate the procedure. Carry on with this iteration until reaching the square root of 'n'.
Once the procedure is finished, all untagged numbers within the array are identified as prime numbers. The method successfully filtered out the composite numbers, retaining solely the prime numbers.
The Eratosthenes' Sieve proves to be remarkably effective in identifying prime numbers, particularly with extensive number ranges, as it circumvents costly prime testing for each number separately. It follows a methodical approach of sieving out multiples of established primes to unveil fresh prime numbers.
Program-1:
This is a C++ code example that demonstrates the Sieve of Eratosthenes algorithm for identifying all prime numbers within a specified limit 'n'. The implementation employs a fundamental technique utilizing a boolean vector to distinguish between prime and non-prime numbers:
#include <iostream>
#include <vector>
using namespace std;
void sieveOfEratosthenes(int n) {
// Create a boolean vector to mark numbers as prime or non-prime
vector<bool> isPrime(n + 1, true);
// 0 and 1 are, not prime numbers, so mark them as false
isPrime[0] = isPrime[1] = false;
// Start with the first prime number, which is 2
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is true, it means p is prime
if (isPrime[p]) {
// Mark all multiples of p as non-prime
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
// Print the prime numbers
cout << "Prime numbers up to " << n << " are: ";
bool first = true; // To handle the formatting of the output
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
if (first) {
cout << i;
first = false;
} else {
cout << ", " << i;
}
}
}
cout << endl;
}
int main() {
int n;
cout << "Enter the limit (n): ";
cin >> n;
if (n < 2) {
cout << "There are no prime numbers in the specified range." << endl;
} else {
sieveOfEratosthenes(n);
}
return 0;
}
Output
Enter the limit (n): 20
Prime numbers up to 20 are: 2, 3, 5, 7, 11, 13, 17, 19
Explanation:
- The process starts by importing essential libraries: iostream for handling input/output operations and vector for managing a resizable array to hold prime numbers.
- A function named sieveOfEratosthenes is created to execute the Sieve of Eratosthenes technique. This function accepts an integer n as a parameter, indicating the maximum value to discover prime numbers within.
Inside the sieveOfEratosthenes function:
- A boolean vector isPrime is created with a size of n + 1 . Each element of this vector represents a number from 0 to n . Initially, all elements are set to true, assuming that all numbers are prime.
- The elements at indices 0 and 1 in the isPrime vector are explicitly set to false because 0 and 1 are not prime numbers.
- The main part of the algorithm starts with a for loop that iterates from 2 to the square root of n (p * p <= n) . This loop is responsible for finding prime numbers.
Inside the loop:
- If isPrime[p] is true, it means that p is a prime number.
- After that, we enter another loop that starts from p * p and increments by p . This inner loop marks all multiples of p as non-prime by setting the corresponding elements in the isPrime vector to false. It eliminates numbers that are multiples of known prime numbers .
- After the outer loop completes, the isPrime vector contains true for prime numbers and false for non-prime numbers.
- Finally, the code prints out the prime numbers up to n in a human-readable format. A first variable is used to handle the formatting of the output (adding commas between prime numbers).
In the main function:
- The user is prompted to enter the limit (n) for finding prime numbers.
- If n is less than 2 , a message is displayed indicating that there are no prime numbers in the specified range.
- Otherwise, the sieveOfEratosthenes function is called to find and print the prime numbers up to n .
Complexity Analysis:
Time Complexity:
Outer Loop: The initial loop within the sieveOfEratosthenes operation runs from 2 to the square root of 'n'. When expressed in Big O notation, this section demonstrates a time complexity of O(sqrt(n)). This is due to the fact that it is sufficient to examine prime numbers within the square root of 'n' in order to remove multiples.
Inner Loop: Nested within the outer loop is an inner loop responsible for identifying the multiples of the current prime number 'p' as non-prime. This inner loop iterates around 'n/p' times for each prime 'p'. As the value of 'p' increases, the quantity of multiples it identifies diminishes. Thus, the total number of iterations for all primes can be estimated as:
n/2 + n/3 + n/4 + ... + n/p
This sequence converges to n multiplied by the sum of reciprocals from 1/2 to 1/p, resulting in approximately n times the logarithm of the logarithm of n under worst-case scenarios.
Combining the time complexities of the outer and inner iterations, the overall time complexity associated with the Sieve of Eratosthenes algorithm can be estimated to be around O(sqrt(n) * log(log(n))).
Space Complexity:
The space efficiency of the Sieve of Eratosthenes algorithm depends on the storage needed for the boolean array named isPrime, which consists of 'n + 1' elements.
Therefore, the algorithm's space complexity is O(n).
Program-2:
An alternative method for applying the Sieve of Eratosthenes algorithm in C++ involves utilizing a more memory-conscious version that consumes less memory. This technique employs a bitset in place of a boolean vector to decrease memory consumption. Below is a C++ code example showcasing this strategy:
#include <iostream>
#include <bitset>
#include <cmath>
using namespace std;
void sieveOfEratosthenes(int n) {
if (n < 2) {
cout << "There are no prime numbers in the specified range." << endl;
return;
}
// Create a bitset to mark numbers as prime or non-prime
bitset<1000001> isPrime;
// Initialize all numbers as prime
isPrime.set();
// 0 and 1 are, not prime numbers, so mark them as non-prime
isPrime[0] = isPrime[1] = 0;
// Start with the first prime number, which is 2
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is true, it means p is prime
if (isPrime[p]) {
// Mark all multiples of p as non-prime
for (int i = p * p; i <= n; i += p) {
isPrime[i] = 0;
}
}
}
// Print the prime numbers
cout << "Prime numbers up to " << n << " are: ";
bool first = true; // To handle the formatting of the output
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
if (first) {
cout << i;
first = false;
} else {
cout << ", " << i;
}
}
}
cout << endl;
}
int main() {
int n;
cout << "Enter the limit (n): ";
cin >> n;
sieveOfEratosthenes(n);
return 0;
}
Output
Enter the limit (n): 50
Prime numbers up to 50 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Explanation:
- The process starts with importing essential libraries: iostream for handling input and output, bitset for storing prime data efficiently, and cmath for arithmetic functions.
- We create the sieveOfEratosthenes function to execute the Sieve of Eratosthenes technique. This function requires an integer n as a parameter, indicating the maximum value for identifying prime numbers within.
Inside the sieveOfEratosthenes function:
- There is a check to handle a special case where 'n' is less than 2 . If 'n' is less than 2, it means there are no prime numbers in the specified range, so a message is displayed, and the function returns early.
- A bitset named isPrime is created with a size of 1000001 . This bitset is used to efficiently mark numbers as prime (1) or non-prime (0). It provides a memory-efficient alternative to boolean vectors.
- All numbers in the isPrime bitset are initialized as prime (set to 1 ) because we start with the assumption that all numbers are prime. We later mark non-prime numbers as 0.
- The numbers 0 and 1 are explicitly marked as non-prime (set to 0) because they are not prime numbers.
- After that, the algorithm proceeds to mark non-prime numbers by starting with the first prime number, which is 2 .
- The core of the Sieve of Eratosthenes algorithm is the part inside the for loop :
- The outer loop iterates from 2 to the square root of 'n' (p * p <= n) . This loop is responsible for finding prime numbers.
Inside the loop:
- If isPrime[p] is true, it means that 'p' is a prime number.
- The inner loop starts from p * p and increments by 'p' . It marks all multiples of 'p' as non-prime by setting the corresponding bits in the bitset to 0 . It eliminates numbers that are multiples of known prime numbers .
- After the outer loop completes, the bitset isPrime contains 1s for prime numbers and 0s for non-prime numbers.
- Finally, the code prints out the prime numbers up to 'n' in a human-readable format. A first variable is used to handle the formatting of the output (adding commas between prime numbers).
In the main function:
- The user is prompted to enter the limit (n) for finding prime numbers.
- The sieveOfEratosthenes function is called to find and print the prime numbers up to 'n' .
- This implementation is memory-efficient due to the use of the bitset and retains the time complexity of approximately O(sqrt(n) * log(log(n))) , making it suitable for finding prime numbers within a given range.
Complexity Analysis:
Time Complexity:
Setting up a bitset with a capacity of 1000001 to represent numbers ranging from 0 to 'n' marks the initialization phase. Although this step requires O(n) time, it can be treated as constant in real-world scenarios owing to the static size of the bitset.
The main component of the algorithm is the external loop, which is in charge of identifying prime numbers. This loop runs around sqrt(n) times (O(sqrt(n))) to determine primes. This approach is based on the fact that numbers greater than the square root of 'n' do not need to be examined when searching for prime numbers.
The nested loop flags multiples of prime numbers as composite, and it executes approximately n log(log(n)) iterations overall. This behavior is due to a reduction in the number of iterations as prime numbers are identified, eventually reaching n log(log(n)) at its most inefficient point.
The overall time complexity is represented as O(n + sqrt(n) + n log(log(n))), covering setup, identifying prime numbers, and flagging multiples. In reality, the primary factor is the inner loop's impact, n log(log(n)), which governs the overall complexity. This thorough analysis elucidates the distribution of time among different algorithmic stages, aiding in a holistic grasp of its effectiveness.
Space Complexity:
Bitset for Prime Marking:
- The bitset named isPrime is used to mark numbers as prime (1) or non-prime (0).
- The size of the bitset is fixed at 1000001 , which is sufficiently large to handle numbers up to 'n'.
- Therefore, the space complexity for the bitset is O(1000001) , which can be approximated to O(1) , as it's a constant-size data structure.
Additional Space:
There are extra variables implemented in the code, including integer variables (n, p, i, first, etc.), that consume a fixed quantity of memory space.
Therefore, the space complexity of these variables remains constant at O(1).
