质数判断算法解析：核心原理、流程图及循环条件疑问解答

Hey there! Let's walk through this prime-checking code clearly—you already get the code structure, so we'll focus on the "why" behind it all.

Core Principle of Prime Checking #

First, let's recap the definition of a prime number: a positive integer greater than 1 that has no positive divisors other than 1 and itself. So our goal is simple: verify if there's any number between 2 and (n-1) that divides n evenly. If yes → not prime; if no → prime.

Logic Flow (Step-by-Step) #

Think of this code as following a straightforward decision tree:

• Step 1: Ask the user to input a positive integer n
• Step 2: Initialize a flag variable to 0 (we'll use this as a "red flag"—0 means "prime until proven otherwise", 1 means "definitely not prime")
• Step 3: Handle the special case first: if n is 1, immediately say it's neither prime nor composite (since 1 doesn't fit either category)
• Step 4: For n > 1, loop from i=2 up to i <= n/2:
  • If n % i == 0 (meaning i divides n evenly), set flag to 1 and break out of the loop early—no need to check further!
• Step 5: After the loop, check the flag:
  • If flag is still 0 → no divisors found, so n is prime
  • If flag is 1 → we found a divisor, so n isn't prime

Why Use i <= n/2 as the Loop Condition? #

Great question! Let's use math to explain this:
Suppose n has a divisor a that's greater than n/2. Then the corresponding pair divisor would be b = n/a. Since a > n/2, dividing n by a gives b < 2 (because n/(n/2) = 2). But the smallest divisor we check is 2—so any divisor larger than n/2 would have a pair smaller than 2, which we don't need to check (since 1 isn't considered here).

In short: checking up to n/2 is sufficient to find any possible divisors (other than n itself, which is allowed for primes). This cuts the number of loop iterations in half, making the code more efficient. For example, if n=100, we only loop up to 50 instead of 99—huge difference!

Can We Replace It With i <= n? #

Technically, yes—but it's a bad idea for two reasons:

1. Efficiency: You'd be looping way more times than needed. For n=1000, you'd loop 998 times instead of 499.
2. Logical Error: If you set the loop to i <= n, when i reaches n, n % i == 0 will always be true. That means your flag will get set to 1 even for prime numbers (since every number is divisible by itself). You'd have to adjust the loop to i <= n-1 to fix this, but you're still wasting cycles checking numbers that can't possibly be divisors (as we explained with the n/2 logic).

Quick Code Recap (With Annotations) #

Here's the code with comments to tie everything together:

#include <stdio.h>
int main() {
    int n, i, flag = 0;
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    // Loop from 2 to n/2 to check for divisors
    for (i = 2; i <= n / 2; ++i) {
        // If any i divides n evenly, it's not a prime
        if (n % i == 0) {
            flag = 1; // Flip the flag to mark non-prime
            break; // No need to check further—exit loop early
        }
    }

    // Handle special case for 1
    if (n == 1) {
        printf("1 is neither prime nor composite.");
    } else {
        // Check the flag to determine the result
        if (flag == 0)
            printf("%d is a prime number.", n);
        else
            printf("%d is not a prime number.", n);
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Balaji Sivasakthi