Sieve of Eratosthenes in C++
In C++, a technique for locating prime numbers is called the Sieve of Eratosthenes. It is used to systematically sieve away the non-prime numbers and leave just the prime numbers remaining eliminates multiples of each prime number. Multiples of each prime number are removed from a list of numbers, leaving only the prime numbers. In this way, Finding prime numbers is effective.
Working of the Sieve of Eratosthenes:
- Boolean arrays and vectors of size n + 1 (where n is the upper limit) should be created, with all values set to true. Numbers will be classified as prime or non-prime using this array.
- Start with number 2, which is the first prime. Mark all multiples of 2 as non-prime by setting their respective array values to false because 2 is a prime.
- The following unmarked number is 3. Find it. Mark all multiples of 3 as non-prime, as 3 is a prime number.
- For every unmarked number up to the square root of n, repeat this procedure. Mark all multiples of the unmarked number p as non-prime when you discover it.
- The array's unmarked numbers are prime numbers when the method is finished.
Example:
Let's find prime numbers up to 10 using the Sieve of Eratosthenes:
Step 1: List the digits from 2 to 10 in this order: 2, 3, 4, 5, 6, 7, 8, 9, 10.
Step 2: As the first number in the list and a prime number, start with 2. Remove all multiples of two from the list (apart from two itself): 4, 6, 8, 10.
Step 3: Continue to the third prime number, 3. Remove 6, 9, and all other multiples of 3 (apart from 3) from the list.
Step 4: Skip 4 because it is already designated as a multiple of two.
Step 5: Go to the prime number 5. Except for 5, remove all multiples of 5 from the list: 10.
Step 6: Omit Step 6, which has already been noted as a multiple of 2 and 3.
Step 7: Go to the prime number 7. When there are no more unmarked integers bigger than 7, the process is finished.
Step 8: The first ten prime numbers are 2, 3, 5, and 7.
Algorithm:
Begin
Declare an array of size n and initialize it to zero
Declare length, i, j
Read length
Declare an array isPrime of size length + 1 and initialize all elements to true
For i = 2 to length, do
If isPrime[i] is true, then
For j = i * i to length step, i do
isPrime[j] = false
End For
End If
End For
Print "Prime numbers up to " + length + " are:"
For i = 2 to length, do
If isPrime[i] is true, then
Print i
End If
End For
End
Program:
Let's take an example to demonstrate the Sieve of Eratosthenes in C++.
#include <iostream>
#include <vector>
using namespace std;
void sieve of Eratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
cout << "Prime numbers up to " << n << " are:" << endl;
for (int p = 2; p <= n; p++) {
if (isPrime[p]) {
cout << p << " ";
}
}
cout << endl;
}
int main() {
int n;
cout << "Enter a number to find all prime numbers up to that number: ";
cin >> n;
sieveOfEratosthenes(n);
return 0;
}
Output:
![Sieve of Eratosthenes in C++](https://static.tutorialandexample.com/cpp/sieve-of-eratosthenes-in-cpp1.png)
The following provides a thorough explanation of how the offered C++ software operates:
1. Initialization of a vector:
- In this example, we define a boolean vector named isPrime to indicate if an integer is prime or not. The prime number tracking vector is employed.
- The vector starts with a size of n + 1, where n is the user-supplied maximum limit.
- Assuming that all starting numbers are prime, the isPrime vector is started with all elements set to true.
2. Implementation of the Sieve Algorithm:
- The computer program begins iterating from 2 (the initial prime number) to n squared.
- It is because if a number p is not prime, smaller prime numbers would have already designated its multiples less than p * p as non-prime.
- The isPrime[p] function is tested inside the loop which determines whether p is a prime number.
- In that case, it goes on to set isPrime[i] to false for each i in the range from p * p to n, designating all multiples of p as non-prime. Non-prime numbers are efficiently removed in this stage.
3. Printing Prime Numbers:
- All prime numbers discovered are printed by the application after the sieve method is finished.
- It begins by printing a message containing the maximum value of n.
- After that, it checks whether isPrime[p] is true by iterating through the isPrime vector from 2 to n. If so, it prints p because it indicates that p is a prime number.
- Finally, it prints a newline character at the end to properly format the result.
4. Main Function:
- The beginning of the program serves as its primary function.
- It asks the user to specify an integer (n) that represents the maximum number of prime integers that can be found.
- It employs cin to read user input.
- After that, the user-supplied value of n is passed as an input when the sieveOfEratosthenes function is called.
- Finally, it returns 0 to show that the program has run successfully.
When compiling and running this application, the Sieve of Eratosthenes algorithm will locate and output all prime integers up to the specified upper limit (n).
This C++ application searches for and prints all prime numbers up to a user-specified limit (n) using the Sieve of Eratosthenes algorithm. After that, the prime numbers are printed after using a boolean vector to distinguish between prime and non-prime values.