Efficient Prime Number Generation in C++: A Comprehensive Guide from Basics to Optimizations

Introduction

Prime numbers hold a fundamental role in computer science and mathematics, with applications in encryption, algorithm design, and more. Efficient algorithms for generating primes not only enhance program performance but also deepen understanding of number theory and computational complexity. Based on Q&A data and reference articles, this article systematically introduces multiple methods to generate prime numbers less than 100 in C++, focusing on optimization strategies and common errors.

Prime Number Definition and Basic Algorithm

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. According to this definition, the most straightforward algorithm checks if a number is divisible by any integer from 2 to n-1. For example, for the number 5, it checks divisibility by 2, 3, and 4; since none divide 5, it is prime. Although intuitive, this method has a high time complexity of O(n²), making it inefficient for large n.

Square Root Optimization Principle

The key to optimizing the algorithm lies in reducing unnecessary checks. Mathematically, if n has a divisor d, then it must have another divisor n/d. If d ≤ √n, then n/d ≥ √n, so it suffices to check integers from 2 to √n. For instance, for n=100, √100=10; if 100 is not divisible by any number from 2 to 10, it must be prime. This significantly reduces the inner loop iterations, optimizing time complexity to O(n√n).

Method 1: Conditional Optimization

The first method directly applies the square root condition in the inner loop. Code example:

int main() {
    for (int i = 2; i < 100; i++) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) 
                break;
            else if (j + 1 > sqrt(i)) {
                cout << i << " ";
            }
        }
    }
    return 0;
}

This code uses j * j <= i to implement the square root check, avoiding floating-point operations. When the inner loop completes without finding a divisor, it outputs the prime. However, the condition else if (j + 1 > sqrt(i)) may be imprecise due to floating-point errors. Improvement suggestion: use integer comparisons, such as directly checking if j reaches the boundary.

Method 2: Boolean Flag Control

The second method introduces a boolean variable to track prime status, improving readability and correctness:

int main() {
    for (int i = 2; i < 100; i++) {
        bool prime = true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                prime = false;
                break;
            }
        }
        if (prime) cout << i << " ";
    }
    return 0;
}

This approach separates the checking and output logic, reducing errors. The boolean variable prime is initially true; if a divisor is found, it is set to false and the loop breaks. Finally, the number is output only if prime is true. The code is clearer and easier to debug and extend.

Method 3: Pre-stored Prime List Method

The third method further optimizes by utilizing a list of previously computed primes:

#include <vector>
int main() {
    std::vector<int> primes;
    primes.push_back(2);
    for (int i = 3; i < 100; i++) {
        bool prime = true;
        for (int j = 0; j < primes.size() && primes[j] * primes[j] <= i; j++) {
            if (i % primes[j] == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            primes.push_back(i);
            cout << i << " ";
        }
    }
    return 0;
}

This method is based on the number theory principle: if a number is divisible by a non-prime, it must be divisible by some prime. By storing known primes, the inner loop checks only these primes, reducing computation. For example, for i=15, it checks primes 2 and 3, and since 3 divides 15, it is not prime. Performance improves significantly, especially for large ranges.

Common Errors and Corrections

In the Q&A data, a user tried for (int j=2; j<sqrt(i); j++) but failed, due to reasons such as: 1) sqrt(i) returns a float, potentially missing the integer part of √n; 2) improper boundary handling; j * j <= i should be used to ensure inclusion of the equality case. Corrected code, as in Method 2, avoids floating-point issues and enhances robustness.

Performance Comparison and Summary

The three methods show increasing efficiency: Method 1 is basic but error-prone, Method 2 is stable and reliable, and Method 3 is optimal. For n=100, Method 3 checks only a few primes, while Methods 1 and 2 check more numbers. In practice, Method 3 suits large-scale prime generation, while Method 2 is ideal for education and small tasks. Understanding these algorithms aids in developing efficient, maintainable code.

Extensions and Resources

For further learning, refer to the Sieve of Eratosthenes, which efficiently generates prime lists by marking multiples. Reference articles provide implementations in multiple languages, facilitating cross-platform application. Practical advice: write test cases to verify output, e.g., ensuring 2, 3, 5, 7 are correctly identified as primes.