C++ Program to Find All Prime Numbers in Range (Sieve Method) with Explanation
C++
Hard
Control Flow
38 views
1 min read
197 words
This problem helps you practice core C++ fundamentals in a practical way. It builds intuition around all, prime, method. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Find all prime numbers between 1 and N efficiently.
Real Life: Used in cryptography and security.
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)
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.
Step-by-Step Logic
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.
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
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;
}
Output Example
Output:
2 3 5 7 11 13 17 19
Common Mistakes
- Treating 1 as prime.
- Checking divisibility up to n instead of sqrt(n).
- Missing negative/zero inputs handling.
Solution Guide
Problem
Find all prime numbers between 1 and N efficiently.
Real Life: Used in cryptography and security.
Input / Output
Output
All prime numbers between 1 and N (space separated).
Constraints
• N ≥ 2
• Efficient method required (better than checking each number fully)
Examples
Output:
2 3 5 7 11 13 17 19
Explanation
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.
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.
Details
Common Mistakes
- Treating 1 as prime.
- Checking divisibility up to n instead of sqrt(n).
- Missing negative/zero inputs handling.
Official Solution
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;
}
Solutions (0)
No solutions submitted yet. Be the first!
