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 !!



Comments

Post a Comment

Popular Posts

Infix to Postfix Expression

-
Infix to Postfix Expression Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands. Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands. PROBLEM STATEMENT : Transform the algebraic expression with brackets into postfix form. Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one f=postfix form (no expressions like a*b*c). Input : t [the number of expressions <= 100] expression [length <= 400] [other expressions] Text grouped in [ ] does not appear in the input file. Output : The expressions in postfix form, one per line. Example Input: 3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d))) Output: abc*+ ab+zx+* at+bac++cd+^* SOLUTION :  Note : We can solve this problem using STACK. Copy Code #include <bits/stdc++.h> int priority(char c) { if(c=='+'|...
Read more

HSL Colors Combination

-
Image
 HSL Colors Combination PROBLEM STATEMENT  Given string str which consists of only 3 letters representing the color,(H) Hue, (S) Saturation, (L) Lightness, called HSL colors. The task is to count the occurrence of ordered triplet “H, S, L” in a given string and give this count as the output. Boundary Condition: 1 <= len(str) <= 1000 Example Input/Output 1: Input: ( ) HHSL Output: 2 Explanation:  There are two triplets of RGB in the given string: => H at index 0, S at index 2, and L at index 3 form one triplet of HSL. => H at index 1, S at index 2, and L at index 3 forms the second triplet of HSL. Example Input/Output 2: Input: ( ) SHL Output: 0 Explanation:  No triplets exist.                                          1)     L EARN THRICE                      ...
Read more

Trailing zeroes in factorial

-
Trailing zeroes in factorial  PROBLEM STATEMENT : Given T testcases and For each testcase an integer N is given as the input. For each input, Find the number of trailing zeroes in N!.    Expected Time Complexity: O(logN) (for Finding Number of trailing Zeroes for each testcase) Expected Auxiliary Space: O(1) Example 1: Input: ( ) 5 Output: 1 Explanation: 5! = 120 so the number of trailing zero is 1. Example 2: Input: ( ) 4 Output: 0 Explanation: 4! = 24 so the number of trailing zero is 0. HINT :     Trailing 0s in n! = Count of 5s in prime factors of n!                 = floor(n/5) + floor(n/25) + floor(n/125) + .. SOLUTION :  Copy Code #include <iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int n,noOfZeroes=0; cin>>n; Trailing 0s in n! = Count of 5s in prime factors of n! while(n>0) { noOfZeroes+=(n/5); n/=5; } ...
Read more