Prime Numbers (Sieve of Eratosthenes)
Prime Numbers ( Sieve of Eratosthenes) The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million (For more understanding, Ref Wiki ). PROBLEM STATEMENT : Given a number n, print all primes smaller than or equal to n. Input : 100 Expected Output : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 SOLUTION : To Solve this problem more effectively, We use Sieve of Eratosthenes algorithm. Time Complexity : O(n*log(log(n))) For Sieve of Eratosthenes algorithm Auxiliary Space : O(n) Here auxiliary space is Boolean Array prime Never Stop Learning !!