Let's say our range is up to 20
    Thus initially declare sieve[21] and all are true.
    sieve[0]=FALSE
    sieve[1]=FALSE
    ------------------------------------------------------------

    sieve[2]=true
    Thus all multiple of 2, needed to be false
    (Of course they are not prime since divisible by 2)
    Thus,
    sieve[4]=FALSE
    sieve[6]=FALSE
    sieve[8]=FALSE
    sieve[10]=FALSE
    sieve[12]=FALSE
    sieve[14]=FALSE
    sieve[16]=FALSE
    sieve[18]=FALSE
    sieve[20]=FALSE
    ------------------------------------------------------------

    sieve[3]=true
    Thus all multiple of 3, needed to be false
    (Of course they are not prime since divisible by 3)
    Thus,
    sieve[6]=FALSE (it was already false though)
    sieve[9]=FALSE
    sieve[12]=FALSE(it was already false though)
    sieve[15]=FALSE
    sieve[18]=FALSE(it was already false though)
    ------------------------------------------------------------

    Sieve[4]=FALSE (Nothing to do more with it)
    ------------------------------------------------------------

    sieve[5]=TRUE
    Thus all multiple of 5, needed to be false
    (Of course they are not prime since divisible by 5)
    Thus,
    sieve[10]=FALSE (it was already false though)
    sieve[15]=FALSE (it was already false though)
    sieve[20]=FALSE (it was already false though)

    In this way, after completing all possible entries we can find
    Only true entries are

    sieve[2]
    sieve[3]
    sieve[5]
    sieve[7]
    sieve[11]
    sieve[13]
    sieve[17]
    sieve[19]

    Others are false.

So now for any given number with in the N

We can tell whether the number is prime or not in O(1) time (based on corresponding TRUE/FALSE value).

When to use this algorithm in programming?

Sieve of Eratosthenes can be very efficient for any program we require to check prime numbers for multiple times (Multiple test cases too).

In such cases, we construct the Sieve of Eratosthenes only single time and for all query each only takes O(1) time reducing the time complexity overall.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	
	cout<<"Enter max range to check for prime numbers\n";
	cin>>n;
	
	bool sieve[n+1];
	
	//sieve of eratosthenes
	memset(sieve,true,sizeof(sieve));//initially all true
	sieve[0]=sieve[1]=false;//0,1 not prime
	for(int i=2;i*i<=n;i++)
		if(sieve[i])
	for(int j=i*2;j<=n;j+=i)//for multiple of i
		sieve[j]=false;//can't be prime

	cout<<"Enter non-negative integer to check prime or not\n";
	cout<<"Negative no to exit\n";
	
	int k;
	cin>>k;
	
	while(k>=0){
		if(sieve[k])
			cout<<k<<" is prime\n";
		else
			cout<<k<<" is not prime\n";

		cout<<"Try more or exit\n";
		cin>>k;
	}
	
	cout<<"Exited\n";
	
	return 0;
}

Output

Enter max range to check for prime numbers
1000
Enter non-negative integer to check prime or not
Negative no to exit
997
997 is prime
Try more or exit 
993
993 is not prime 
Try more or exit 
13 
13 is prime 
Try more or exit 
103
103 is prime
Try more or exit 
111
111 is not prime 
Try more or exit 
-1 
Exited