Sieve of Eratosthenes

Algorithm Explanation

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given number n. It works by iteratively marking the multiples of each prime number starting from 2.

Steps:

1. Create a boolean array is_prime[] of size n+1, initialized as true.
2. Start from the first prime number, p = 2.
3. For each p, mark all multiples of p (from p*p to n) as false.
4. Move to the next unmarked number and repeat until p * p > n.

Time Complexity:

The time complexity is O(n log log n).

Space Complexity:

The space complexity is O(n) due to the boolean array.

Easy Problems

Problem 1: Count Primes Less Than N

Find the number of prime numbers less than a given integer n.

#include <iostream>
#include <vector>
using namespace std;

int countPrimes(int n) {
    vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i)
                is_prime[j] = false;
        }
    }

    int count = 0;
    for (bool prime : is_prime) if (prime) count++;
    return count;
}

int main() {
    int n = 20;
    cout << "Number of primes less than " << n << ": " << countPrimes(n);
    return 0;
}

Problem 2: Print All Primes Less Than N

Print all prime numbers less than a given integer n.

#include <iostream>
#include <vector>
using namespace std;

void sieve(int n) {
    vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i)
                is_prime[j] = false;
        }
    }

    for (int i = 2; i < n; i++) {
        if (is_prime[i]) cout << i << " ";
    }
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Intermediate Problems

Problem 3: Segmented Sieve

Find primes in a range [L, R] using a modified sieve.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void simpleSieve(int limit, vector<int>& primes) {
    vector<bool> is_prime(limit + 1, true);
    for (int p = 2; p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= limit; i += p)
                is_prime[i] = false;
        }
    }
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}

void segmentedSieve(int L, int R) {
    int limit = sqrt(R) + 1;
    vector<int> primes;
    simpleSieve(limit, primes);

    vector<bool> is_prime(R - L + 1, true);

    for (int p : primes) {
        int start = max(p * p, (L + p - 1) / p * p);
        for (int j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }

    for (int i = L; i <= R; i++) {
        if (is_prime[i - L] && i != 1)
            cout << i << " ";
    }
}

int main() {
    int L = 10, R = 50;
    segmentedSieve(L, R);
    return 0;
}

Problem 4: Count Twin Primes Up to N

Twin primes are pairs of primes that differ by 2 (e.g., 11 and 13).

#include <iostream>
#include <vector>
using namespace std;

int countTwinPrimes(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }

    int count = 0;
    for (int i = 2; i <= n - 2; i++) {
        if (is_prime[i] && is_prime[i + 2])
            count++;
    }
    return count;
}

int main() {
    int n = 100;
    cout << "Twin primes up to " << n << ": " << countTwinPrimes(n);
    return 0;
}

Hard Problem

Problem 5: Count Prime Triplets

Find the number of prime triplets (p, p+2, p+6) or (p, p+4, p+6) less than or equal to n.

#include <iostream>
#include <vector>
using namespace std;

int countPrimeTriplets(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }

    int count = 0;
    for (int i = 2; i <= n - 6; i++) {
        if ((is_prime[i] && is_prime[i+2] && is_prime[i+6]) ||
            (is_prime[i] && is_prime[i+4] && is_prime[i+6]))
            count++;
    }
    return count;
}

int main() {
    int n = 100;
    cout << "Prime triplets up to " << n << ": " << countPrimeTriplets(n);
    return 0;
}