How to find all prime number till N? most efficient solution Sieve of Eratosthenes-
There are multiple ways to find prime numbers till N. but the sieve of Eratosthenes is the most efficient solution to find prime numbers till n. This efficient solution often used in competitive programming contests.
algorithm step by step -
step -1 Create a bool vector of size n and initialize it by false value.
step -2 create an empty vector to store prime numbers.
step 3- loop through the visited vector from 2 to n.
step 4- if the current value is pointing to unvisited we will push this value to our answer vector and mark visited it's all multiple till n.
check below image how it works.
Code for most efficient solution Sieve of Eratosthenes in c++