THE SIEVE OF ERATOSTHENES ALGORITHM

The Sieve of Eratosthenes is a classical algorithm designed to efficiently find all prime numbers up to a given natural number n. This algorithm systematically eliminates non-prime numbers from a list, leaving only primes.

This problem can be solved by passing through the loop in the order of 1 - n and checking each number whether it is prime using a function that determines whether to send the number is prime:

Brief Explanation of Prime Numbers:

Prime numbers are natural numbers greater than 1 that have no divisors other than 1 and themselves. They are the building blocks of all natural numbers, and identifying them efficiently is crucial in fields like cryptography, computer science, and number theory.

The Simple Method (isPrime Function)

The simple method involves checking each number individually to determine if it is prime. This is done by iterating through all numbers from 1 to n and using a function that checks if a number has any divisors other than 1 and itself.

bool isPrime(long long n)
{
if(n==1)
return false;
long long d=2;
while(d*d<=n) {
if(n % d == 0)
{
return false;
}
d=d+1;
}
return true;
}

Therefore, the main function would be:

int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
if(isPrime(i)){
cout << i << endl;
}
}
return 0;
}

This method would be too slow for a lot of n, because it checks all the numbers in a row.
This can be accelerated a little if instead of examining the numbers in the order of 1 to n^1/2, we end up with a number that will slightly accelerate the algorithm.

The "isPrime()" function returns true if the number is prime and false otherwise. This method, while straightforward, is inefficient for large values of n because it checks each number in sequence.

As the range of numbers increases, identifying prime numbers through simple methods becomes computationally expensive. Therefore, efficient algorithms like the Sieve of Eratosthenes are essential for quickly determining prime numbers in large datasets.

We will get real acceleration with the Eratosthenes sieve.
Algorithm Eratosthenes sieve:
It is based on the idea that in one pass we check more numbers at once. Assume that n = 50, i.e. that all numbers between 1 and 50 should be checked if they are prime:

Sieve of Eratosthenes Example: Determining the free numbers in the segment 1-50

Figure 1: Sieve of Eratosthenes Example: Determining the prime numbers in the segment 1-50

Let's take the first potential divisor of number 50, which is surely a simple number, and remove from the sequence all the numbers that are shared with this potential sniper. This is number 2. The numbers from the array are folded because they are certainly not prime numbers, because they are divisible by 2, except with 1 and with itself. This could be solved by a loop in which the current variable changes from 2 to 50 ^ 1/2 ~ 7.07 ~ 7. So the last prime number to be divisor is 7. After removing numbers divisible by 2, the state is as follows:

Figure 2: The Sieve of Eratosthenes example-removal of content number 2 that is greater than 2

This procedure is repeated with the next number which is not removed . If the number has not been removed previously, this means that it is prime. So we will now remove all numbers that are greater than 3 and are shared with 3. After that, it will remain:

Figure 3: The Sieve of Eratosthenes example-removal of content number 3 which is greater than 3

So we will now remove all numbers that are greater than 5 and are divisible by 5. After that, it will remain:

Figure 4: The Sieve of Eratosthenes example-removing the common multiple the number 5 that are greater than 5

Figure 4: The Sieve of Eratosthenes example-removal of content number 5 which is greater than 5

It remains to remove all numbers that are larger than 7 and which are divisible by 7. That's in this case only number 49. After that, it will remain:

Figure 5: The Sieve of Eratosthenes example-removal of content number 7 which is greater than 7

The numbers remaining are prime numbers.

The Sieve of Eratosthenes - cod

The function that removes these (not prime) numbers would look like:

void eratosten(int n)
{
for(int i=2; i <= sqrt(n); i++)
{
if(P[i])
{
for(int j=i; j < n/i; j++)
{
P[i*j]=false;
}
}
}
}

The current element in the loop is a delimiter for which we verify that the numbers that are potentially need to be removed are divisible by itself. Remembering the remaining numbers is done using the sequence P. First, we check whether the number that is a potential divisor is still in sequence. If he is, he is a divisor with whom we will remove his content. If not, then this number can not be a divisor because it is not prime.
If it is a divisor, then we perform a check through the loop for numbers starting from the squares of the sender. The x numbers between the divisor and the squares of the divisor (i <x <i * i) have already been checked by the previous divisor and should not be checked. The number of numbers to be removed is obtained as n / i - i. In the previous example, where n = 50, and the divisor 2 it would be 50 / 2 - 2 = 25-2 = 23. This is logical because it has 25 natural numbers that are divisible from 2 to 50, and since we exclude 1 i 2, 23 numbers remain.
We remove the numbers by placing a member of a array at a position equal to the number that is removed to false. After repeating the procedure with all sorts, the sequence will remain true at the position of the prime numbers. Of course, before this procedure, the entire set of P must be initialized. The main method would be:

int main()
{
int n;
cin >> n;
for(int i = 1;i < n;i++) {
P[i]=true;
}
eratosten(n);
for(int i = 1; i <= n; i++)
{
if(P[i])
cout << i << endl;
}
return 0;
}

You should add in the code above the method:

#include
#define DIM 1000
using namespace std;
bool P[DIM+1];

Use of Eratosthenes sieve for Factoring

In order to factor a number n, that is, to split into simple factors, we need to know all the simple factors even if they multiply pk and then the number n can be written in the following form:

Eg. if n = 50

Using the Sieve of Eratosthenes algorithm, we can first determine p1, p2, ... pk, i.e. dividers.
Then, the number n is first divisible by p1, repeating the division as long as the remainder is partitioned with p1, so the further division process is repeated with p2, etc.
Let's look at the example shown at the beginning, for n = 50. In order to factor this factor, we should begin to share this number with its smallest divisor, which is in this case number 2 and repeat the procedure as long as the remainder of the division is still divisible by 2.
1 cycle: 50/2 = 25, the rest is 25
Number 25 can not bi divided by 2 furthermore.
Next, the procedure repeats with the rest, which is number 25 and its smallest divider is 5:
1 cycle: 25/5 = 5, the rest is 5
2 cycles: 5/5 = 1, the remainder is 1
Here the process ends.
We can use the sieve of Eratosthenes algorithm here to determine for each number x its smallest divisor instead of removing it. In the example shown, these would be numbers 2 and 5.
Next, the cycle separation process shown would be done using the loop.
At the beginning, first prepare the arrays:

#include < iostream >
using namespace std;
#include< math.h >
#define DIM 1000
using namespace std;

int D[DIM+1]; // Smallest prime divisor for each number
int a[DIM+1]; // Exponent of each prime factor
int p[DIM+1]; // Prime factors

A function that determines the least divisor of numbers:

void eratosten(int n)
{

for(int i = 1; i <= n; i++)
{

D[i] = i; // Initialize each number to be its own smallest divisor

}
for(int i = 2; i <= sqrt(n); i++) // Adjusted loop condition
{

if(D[i] == i) // Check if i is prime
{

for(int j = i; j <= n/i; j++)
{

// Find the smallest prime divisor for each multiple of i
if(D[i] < D[i*j])

D[i*j] = D[i]; // Update with the smallest divisor

}

In the first loop, he set up the shareholders for all the numbers to be themselves (numbers are shared with oneself). This will remain the smallest particle if it is for free numbers.
Next, for numbers 2 to 2/2, we look at the order of their least divisors. For complex numbers, one that was abolished in their case by their smallest sender, this is the smallest particle, and for the number (i * j). For example, for the number 8, the smallest particle is 2, and the number 8 in the loop is given as 2 * 4, so i = 2, j = 4. In the starting sequence D [8] = 8, D [2] = 2 and after testing conditions if (D [2] <D [2 * 4]) ... the new value D [8] = 2, and the smallest is its divisor.
Now that we know all the smallest dividers, factoring can be done:

int faktoring(int x)
{
int k=0;
while(x > 1)
{
k=k+1;
p[k]=D[x];
a[k]=0;
while(x%p[k]==0)/*Dividing by the smallest divisor while it is possible*/
{
x=x/p[k];
a[k]=a[k]+1;
}
}
return k;
}

The elements of the array p are in the order of the smallest the dividers of that number k to be factorized. In the first iteration of the outer loop, the loop is the initial number k, the second is the remainder of the division that remains after dividing with the smallest divisor through the inner loop length. The process is repeated until it reaches 1.
The use of the sieve of Eratosthenes for factoring is used when we have many numbers to be factorized. For example, if the starting number is to be counted, if all numbers of 2-n are to be factorized, this method is suitable. The main method to do this is:

int main()
{
int n,k;
cin >> n;
eratosten(n);
for(int i = 2; i <= n; i++)
{
k=faktoring(i);
for(int j = 1; j <= k; j++)
{
cout << i << "= " << p[j] << "^" << a[j];
if(j != k)
cout << "*";
else
cout << ";";
}
cout << endl;
}
return 0;
}

Efficiency of the Sieve

The Sieve of Eratosthenes is a highly efficient algorithm for finding all prime numbers up to a given limit n. The efficiency of this algorithm can be evaluated both in terms of time complexity and space complexity:

Time Complexity: The time complexity of the Sieve of Eratosthenes is O(nlog⁡log(⁡n)). This is derived from the fact that each prime number p will mark multiples of p as non-prime, and the number of such multiples is approximately n/p. When summed over all primes, this results in the O(nlog⁡log⁡n) complexity, making it significantly faster than the naive approach of checking each number individually for primality.
Space Complexity: The space complexity of the algorithm is O(n), primarily due to the storage of the boolean array P[] that keeps track of whether each number up to n is prime. This is relatively efficient for moderate values of n, but can become a limiting factor as n grows very large.

This efficiency in both time and space is why the Sieve of Eratosthenes is preferred for generating a list of primes, especially when compared to simpler methods like trial division, which has a time complexity of O(n\sqrt{n}).

Limitations

While the Sieve of Eratosthenes is efficient for finding primes up to moderate values of n, it does have limitations, particularly when dealing with very large numbers:

Memory Constraints: The algorithm requires O(n) space to store the boolean array P[ ]. For very large values of n, this can consume a significant amount of memory, which may not be feasible on systems with limited resources.
Alternatives for Large Ranges: For extremely large values of n, or when memory is a constraint, an alternative approach like the Segmented Sieve can be used. The segmented sieve divides the range [1,n] into smaller segments and applies the sieve algorithm to each segment individually. This reduces the memory requirement because only a segment of the range is stored in memory at any one time.
Another alternative is the Wheel Factorization technique, which optimizes the sieve by skipping multiples of the smallest primes (e.g., 2, 3, 5) in the initial steps, reducing the number of operations required.

Previous
|< A prime numbers and factoring

Next
The Euclidean algorithm >|