埃拉托斯特尼筛法实现异常：《Programming Principles and Practice using C++》习题问题

Hey there! Let's work through your Sieve of Eratosthenes problem together. I remember how easy it is to get tripped up by nested loops and flagging logic when you're starting out with this algorithm—so don't worry, we'll get it sorted.

First, let's recap the core idea of the Sieve: we create a boolean array to track which numbers are prime, mark non-primes by eliminating multiples of each prime we find, then output the remaining unmarked numbers. Common pitfalls here usually involve incorrect loop ranges, misinitializing the array, or messing up the marking step.

A Working Example of the Sieve for Primes Under 100 #

Let's start with a correct implementation you can compare your code against:

#include <iostream>
#include <vector>

int main() {
    const int max_num = 100;
    // Initialize all entries as true (assume all are prime initially)
    std::vector<bool> is_prime(max_num + 1, true);
    // 0 and 1 are not primes
    is_prime[0] = is_prime[1] = false;

    // Loop through each number starting from 2
    for (int i = 2; i * i <= max_num; ++i) {
        // If current number is still marked prime
        if (is_prime[i]) {
            // Mark all multiples of i as non-prime
            // Start from i*i (smaller multiples already marked by smaller primes)
            for (int j = i * i; j <= max_num; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Print all primes
    std::cout << "Primes between 2 and 100:\n";
    for (int num = 2; num <= max_num; ++num) {
        if (is_prime[num]) {
            std::cout << num << " ";
        }
    }
    std::cout << "\n";

    return 0;
}

Common Issues to Check in Your Code #

Here are the most likely places your code might be going wrong:

• Incorrect array initialization: Did you set is_prime[0] and is_prime[1] to false? Forgetting this will include 0/1 in your output.
• Inner loop starting point: If you started marking multiples from 2 instead of i*2 or i*i, you might be marking the prime number itself as non-prime.
• Loop termination condition: Using i <= max_num instead of i*i <= max_num works, but it's inefficient—and if your logic isn't handling the later iterations correctly, it could cause unexpected marks.
• Goto/boolean flag misuse: When using goto to exit nested loops, you might be breaking out too early (before finishing marking all multiples). With boolean flags, if you forgot to reset the flag between iterations, you could skip valid primes or mark valid primes as non-prime.

Compare your code line by line with the example above—chances are the issue is in one of these areas. If you still can't spot it, feel free to share your exact code, and we can dive deeper!

内容的提问来源于stack exchange，提问作者Aaron McAnally