The Sieve of Eratosthenes

To efficiently determine primes within a range, the Sieve of Eratosthenes is a classic algorithm. The process involves creating an array where each index represents a number. Initially, all entries are marked as potential primes (1). We then iterate starting from 2; if a number is identified as prime, we mark all its multiples in the array as non-prime (0).

Static Implementation (Fixed Size)

We begin with a fixed limit, such as 1000. The implementation initializes an array, iterates through numbers, marks multiples, and finally prints the candidates.

#include <stdio.h>
#define LIMIT 1000

int main() {
    int k, l, primeFlags[LIMIT];

    // Initialize all numbers as potential primes
    for (k = 2; k < LIMIT; k++) {
        primeFlags[k] = 1;
    }

    // Mark non-primes
    for (k = 2; k < LIMIT; k++) {
        if (primeFlags[k]) {
            for (l = k; k * l < LIMIT; l++) {
                primeFlags[k * l] = 0;
            }
        }
    }

    // Output results
    for (k = 2; k < LIMIT; k++) {
        if (primeFlags[k]) {
            printf("%4d ", k);
        }
    }
    printf("\n");
    return 0;
}

User Input Handling

To verify a specific number entered by the user, we utilize standard input. After populating our sieve array, we simply check the status of the requested index. While a switch statement can be used based on the binary flag, an if-else construct offers clearer intent for this decision-making flow.

// Check user input against precomputed flags
if (primeFlags[targetNumber]) {
    printf("%d is a prime number.\n", targetNumber);
} else {
    printf("%d is not a prime number.\n", targetNumber);
}

Common pitfalls include accessing indices outside the allocated range. Ensure the input value falls within the bounds [2, LIMIT].

Optimization: Dynamic Memory Allocationn

Fixed arrays consume stack space or static memory limits, which become problematic when the required range increases significantly (e.g., 10^5 or higher). To handle larger datasets flexibly, we can use dynamic memory allocation via stdlib.h. This allows us to define the size based on runtime arguments rather than compile-time macros.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    long int limit, m, counter;
    int targetNum;

    // Parse range from command line argument
    if (argc < 2) {
        printf("Usage: %s <limit>\n", argv[0]);
        return 1;
    }
    limit = atol(argv[1]);

    // Allocate memory dynamically
    int *flags = (int*) malloc(limit * sizeof(int));
    if (flags == NULL) {
        printf("Error: Insufficient memory.\n");
        return 1;
    }

    // Read the specific number to test
    scanf("%d", &targetNum);

    // Initialize array
    for (m = 2; m < limit; m++) {
        flags[m] = 1;
    }

    // Execute Sieve logic
    for (m = 2; m < limit; m++) {
        if (flags[m]) {
            for (counter = m; m * counter < limit; counter++) {
                flags[m * counter] = 0;
            }
        }
    }

    // Validate result
    if (flags[targetNum]) {
        printf("%d is a prime number.\n", targetNum);
    } else {
        printf("%d is not a prime number.\n", targetNum);
    }

    // Free allocated memory
    free(flags);
    return 0;
}

Performance Considerations and Alternatives

While dynamic allocation solves the memory sizing issue, extremely large ranges may still cause Time Limit Exceeded (TLE) errors due to the O(N log log N) complexity of the Sieve. Furthermore, allocating large contiguous blocks of memory can be costly.

For scenarios involving only single-number verification rather than batch generation, a direct trial division method is often more efficient regarding memory footprint, though potentially slower for very large numbers. The algorithm checks divisibility from 2 up to sqrt(n).

#include <stdio.h>
#include <math.h>

int main() {
    int inputValue;
    int isComposite = 0;

    if (scanf("%d", &inputValue) != 1) {
        return 1;
    }

    // Edge cases: 0, 1, negative are not primes
    if (inputValue <= 1) {
        printf("%d is not a prime number.\n", inputValue);
        return 0;
    }

    // Check for factors
    for (int k = 2; k * k <= inputValue; k++) {
        if (inputValue % k == 0) {
            isComposite = 1;
            break;
        }
    }

    if (isComposite) {
        printf("%d is not a prime number.\n", inputValue);
    } else {
        printf("%d is a prime number.\n", inputValue);
    }

    return 0;
}