Overview

The Sieve of Eratosthenes is an efficient ancient algorithm for finding all prime numbers up to a specified integer n. It works by iterative marking the multiples of each prime number as composite (non-prime), starting from the first prime number, 2.

Algorithm Steps

Consider finding all primes up to 25:

1. Initialization: Create a list of consecutive integers from 2 to 25.

• 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

8. First Pass (p = 2): Mark 2 as prime. Eliminate all multiples of 2 (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24).

• Remaining: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25

10. Second Pass (p = 3): The next unmarked number is 3. Mark 3 as prime and eliminate multiples of 3 (9, 15, 21).

• Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25

12. Termination Condition: The algorithm terminates when p² > n. Since 5² = 25 is not greater than 25, we continue.
13. Third Pass (p = 5): Mark 5 as prime. Eliminate 25.

• Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23

15. Completion: Since 23 < 5², all remaining unmarked numbers are prime. Final Result: Primes up to 25 are: 2, 3, 5, 7, 11, 13, 17, 19, 23.

C++ Implementation

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int limit;
    cout << "Enter upper bound: ";
    cin >> limit;
    
    // Initialize all numbers as potential primes
    vector<bool> primeStatus(limit + 1, true);
    primeStatus[0] = primeStatus[1] = false;
    
    // Sieve process
    for (int current = 2; current * current <= limit; current++) {
        if (primeStatus[current]) {
            // Mark all multiples as composite
            for (int multiple = current * current; multiple <= limit; multiple += current) {
                primeStatus[multiple] = false;
            }
        }
    }
    
    // Output results
    cout << "Prime numbers up to " << limit << ":" << endl;
    for (int num = 2; num <= limit; num++) {
        if (primeStatus[num]) {
            cout << num << " ";
        }
    }
    cout << endl;
    
    return 0;
}
</bool></cmath></vector></iostream>

Plane Division Problem

Problem Statement

Given n straight lines in a 2D plane, determine the maximum number of regions the plane is divided into. Lines are defined by their equations y = kx + b, where k is the slope and b is the y-intercept.

Key Observations

• Duplicate Lines: If a line is identical to a previous one, it doesn't create new regions.
• Base Addition: Each new unique line adds at least one region.
• Interscetion Points: Each unique intersection point with existing lines adds one more region.

Solution Strategy

For each new line, count the number of unique intersection points with all previous lines. The regions added equal the number of unique intersections plus one.

C++ Implementation

#include <iostream>
#include <set>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int lineCount;
    cin >> lineCount;
    
    vector<pair double="">> coefficients(lineCount);
    vector<bool> isDuplicate(lineCount, false);
    long long regionCount = 1; // Start with 1 region (empty plane)
    
    for (int i = 0; i < lineCount; i++) {
        cin >> coefficients[i].first >> coefficients[i].second;
        
        set<pair double="" long="">> intersections;
        
        for (int j = 0; j < i; j++) {
            if (isDuplicate[j]) continue;
            
            // Check for parallel lines (same slope)
            if (coefficients[i].first == coefficients[j].first) {
                if (coefficients[i].second == coefficients[j].second) {
                    isDuplicate[i] = true;
                    break;
                }
                continue; // Parallel but distinct - no intersection
            }
            
            // Calculate intersection point
            long double xIntersect = (coefficients[j].second - coefficients[i].second) / 
                                     (coefficients[i].first - coefficients[j].first);
            long double yIntersect = coefficients[i].first * xIntersect + coefficients[i].second;
            
            intersections.insert({xIntersect, yIntersect});
        }
        
        if (!isDuplicate[i]) {
            regionCount += intersections.size() + 1;
        }
    }
    
    cout << regionCount << endl;
    
    return 0;
}
</pair></bool></pair></vector></utility></set></iostream>

C++ Pair Container

Introduction

The std::pair is a template class in C++ that allows storing two heterogeneous values as a single unit. It is particularly useful when a function needs to return two values or when storing key-value pairs.

Declaration and Initialization

#include <utility>

// Direct initialization
pair<string int=""> person("Alice", 25);
pair<int int=""> coordinates(10, 20);
pair<double char=""> measurement(3.14, 'A');

// Using make_pair
pair<int int=""> point = make_pair(100, 200);
pair<string double=""> product = make_pair("Widget", 19.99);
</string></int></double></int></string></utility>

Accessing Elements

Pair elements are accessed via first and second public members:

pair<string int=""> employee("John", 50000);

cout << "Name: " << employee.first << endl;
cout << "Salary: " << employee.second << endl;
</string>

Returning Multiple Values from Functions

#include <utility>

pair<int bool=""> divideNumbers(int a, int b) {
    if (b == 0) {
        return make_pair(0, false);
    }
    return make_pair(a / b, true);
}

int main() {
    auto result = divideNumbers(10, 3);
    if (result.second) {
        cout << "Quotient: " << result.first << endl;
    }
    return 0;
}
</int></utility>

Simplifying Type Declarations

Use typedef or type aliases to simplify repeated pair declarations:

typedef pair<string string=""> Author;

Author writer1("George", "Orwell");
Author writer2("Jane", "Austen");

// C++11 and later
using Coordinate = pair<double double="">;
Coordinate location(45.5, -122.6);
</double></string>

Nested Pairs

For storing three values, pairs can be nested:

// Note: space between >> brackets in older C++ standards
pair<int int="" pair="">> triplet = make_pair(1, make_pair(2, 3));

cout << triplet.first;           // 1
cout << triplet.second.first;    // 2
cout << triplet.second.second;   // 3
</int>

Binary Indexed Tree (Fenwick Tree)

For advanced range query operations and point updates, the Binary Indexed Tree (also known as Fenwick Tree) provides an efficient data structure with O(log n) time complexity for both operations. This structure is particularly useful for problems involving prefix sums and range queries on mutable arrays.

Key operations include:

• Update: Modify a single element in O(log n)
• Query: Get prefix sum in O(log n)
• Range Query: Get sum of any interval using two prefix queries