C++中如何使用for循环找出2到输入整数N间的所有合数？

Alright, let's tackle this problem step by step. You need a C++ program that takes an integer N as input, then outputs all composite numbers in the range from 2 to N. Since you already have logic to check for prime numbers, we can repurpose that to identify composites easily—after all, composite numbers are positive integers greater than 1 that are not prime (remember, 1 is neither prime nor composite).

Method 1: Use a Prime Checker (Simple & Straightforward) #

This approach leverages a helper function to check if a number is prime, then iterates through the range and collects numbers that aren't prime.

Step 1: Write the Prime Check Function #

First, let's define a isPrime function that returns true if a number is prime, false otherwise:

#include <iostream>
// Using std:: prefix instead of 'using namespace std;' for cleaner code boundaries
bool isPrime(int num) {
    if (num <= 1) return false;       // Numbers ≤1 aren't prime
    if (num == 2) return true;        // 2 is the only even prime
    if (num % 2 == 0) return false;   // Even numbers >2 aren't prime
    // Check divisors from 3 up to sqrt(num), stepping by 2 (only odd divisors)
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Step 2: Main Program to Collect Composites #

Now, in the main function, we'll read N, loop through 2 to N, and print any number that isn't prime:

int main() {
    int n;
    std::cout << "Enter an integer N: ";
    std::cin >> n;

    if (n < 4) { // The smallest composite number is 4
        std::cout << "No composite numbers in this range." << std::endl;
        return 0;
    }

    std::cout << "Composite numbers between 2 and " << n << " are:\n";
    for (int num = 2; num <= n; ++num) {
        // If the number isn't prime, it's a composite (since we skip 1)
        if (!isPrime(num)) {
            std::cout << num << " ";
        }
    }
    std::cout << std::endl;
    return 0;
}

Example Output

If you input 10, the program will output:

Composite numbers between 2 and 10 are:
4 6 8 9 10 

Method 2: Sieve of Eratosthenes (Efficient for Large N) #

If you're working with large values of N (like 10,000 or more), the Sieve of Eratosthenes is much faster. It marks all prime numbers in the range first, then we just collect the unmarked numbers (composites).

Code Implementation #

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cout << "Enter an integer N: ";
    std::cin >> n;

    if (n < 4) {
        std::cout << "No composite numbers in this range." << std::endl;
        return 0;
    }

    // Create a boolean vector where index represents the number, value is true if prime
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 aren't primes

    // Mark non-primes using the sieve
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // Mark all multiples of i starting from i*i as non-prime
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // Print all non-prime numbers (composites)
    std::cout << "Composite numbers between 2 and " << n << " are:\n";
    for (int num = 2; num <= n; ++num) {
        if (!isPrime[num]) {
            std::cout << num << " ";
        }
    }
    std::cout << std::endl;
    return 0;
}

This method has a time complexity of O(n log log n), which is way more efficient than checking each number individually for large N.

内容的提问来源于stack exchange，提问作者Kenneth Steven McAusland Jr.