Find All Prime Numbers in Range (Sieve Method)
Hard
C++
Control Flow
39 views
Problem Statement
Find all prime numbers between 1 and N efficiently.
Real Life: Used in cryptography and security.
Real Life: Used in cryptography and security.
Input Format
An integer N.
Output Format
All prime numbers between 1 and N (space separated).
Example
20
2 3 5 7 11 13 17 19
Constraints
• N ≥ 2
• Efficient method required (better than checking each number fully)
• Efficient method required (better than checking each number fully)
Concept Explanation
Prime numbers are numbers greater than 1 that have only two divisors: 1 and itself.
To find primes efficiently, we avoid unnecessary checks.
To find primes efficiently, we avoid unnecessary checks.
Step-by-Step Explanation
1.Take input N.
2.Loop number i from 2 to N.
3.Assume current number i is prime.
4.Check divisibility of i from 2 to √i.
5.If i is divisible by any number:
• Mark it as not prime and stop checking.
6.If no divisor is found:
• Print i as a prime number.
7.Continue until all numbers up to N are checked.
2.Loop number i from 2 to N.
3.Assume current number i is prime.
4.Check divisibility of i from 2 to √i.
5.If i is divisible by any number:
• Mark it as not prime and stop checking.
6.If no divisor is found:
• Print i as a prime number.
7.Continue until all numbers up to N are checked.
Concept Explanation
Prime numbers are numbers greater than 1 that have only two divisors: 1 and itself.
To find primes efficiently, we avoid unnecessary checks.
To find primes efficiently, we avoid unnecessary checks.
Step-by-Step Explanation
1.Take input N.
2.Loop number i from 2 to N.
3.Assume current number i is prime.
4.Check divisibility of i from 2 to √i.
5.If i is divisible by any number:
• Mark it as not prime and stop checking.
6.If no divisor is found:
• Print i as a prime number.
7.Continue until all numbers up to N are checked.
2.Loop number i from 2 to N.
3.Assume current number i is prime.
4.Check divisibility of i from 2 to √i.
5.If i is divisible by any number:
• Mark it as not prime and stop checking.
6.If no divisor is found:
• Print i as a prime number.
7.Continue until all numbers up to N are checked.
Input / Output Format
Input Format
An integer N.
Output Format
All prime numbers between 1 and N (space separated).
Constraints
• N ≥ 2
• Efficient method required (better than checking each number fully)
• Efficient method required (better than checking each number fully)
Examples
Input:
20
Output:
2 3 5 7 11 13 17 19
Example Solution (Public)
void control_q15_sieve_primes() {
int n = 30;
bool isPrime[31];
// Initially mark all as prime
for(int i = 0; i <= n; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false; // 0 and 1 not prime
// Sieve algorithm
for(int i = 2; i * i <= n; i++) {
if(isPrime[i]) {
// Mark all multiples as not prime
for(int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
cout << "Prime numbers from 1 to " << n << ": ";
for(int i = 2; i <= n; i++) {
if(isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
Official Solution Code
void control_q15_sieve_primes() {
int n = 30;
bool isPrime[31];
// Initially mark all as prime
for(int i = 0; i <= n; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false; // 0 and 1 not prime
// Sieve algorithm
for(int i = 2; i * i <= n; i++) {
if(isPrime[i]) {
// Mark all multiples as not prime
for(int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
cout << "Prime numbers from 1 to " << n << ": ";
for(int i = 2; i <= n; i++) {
if(isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
Please login to submit solutions.