Find All Prime Numbers in Range (Sieve Method)
C++
Hard
2 views
Problem Description
Find all prime numbers between 1 and N efficiently.
Real Life: Used in cryptography and security.
Step-by-Step Logic:
1. Create array marking all numbers as prime initially
2. Start from 2 (first prime)
3. Mark all multiples of 2 as not prime
4. Move to next unmarked number (next prime)
5. Repeat until all checked
6. Print all marked primes
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!
No comments yet. Start the discussion!