Algorithm Analysis and Optimization for Printing Prime Numbers from 1 to 100 in C

Problem Background and Code Analysis

Printing prime numbers between 1 and 100 is a common exercise in C programming. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The original code provided by the questioner attempted to achieve this using nested loops but encountered a critical issue: it failed to print the smallest prime number, 2, and started output from 3 instead.

The original code is as follows:

#include <stdio.h>
int main(void)
{
    for(int i=2;i<100;i++)
    {
        for(int j=2;j<i;j++)
        {
            if(i%j==0)
                break;
            else if(i==j+1)
                printf("%d\n",i);
        }
    }
}

This code uses two nested for loops. The outer loop iterates through integers from 2 to 99, while the inner loop checks whether each number is prime. However, the inner loop condition j<i and the conditional check i==j+1 introduce logical flaws.

Detailed Explanation of Logical Errors

When i=2, the inner loop initializes with j=2, but the loop condition j<i (i.e., 2<2) evaluates to false. Consequently, the inner loop does not execute at all, completely skipping the processing of the number 2 and preventing any conditional checks.

Even if the inner loop were to execute, the condition i==j+1 is poorly designed. This condition attempts to identify i as prime when j has iterated up to i-1 without finding a divisor. However, for i=2, j can only be 2, which does not satisfy i==j+1 (i.e., 2==3), so 2 would still not be printed.

Optimized Solution

Based on the best answer, the optimized code is:

#include <stdio.h>
int main(void)
{
    for (int i=2; i<100; i++)
    {
        for (int j=2; j<=i; j++)   // Modified upper bound
        {
            if (i == j)  // Modified condition and adjusted if order
                printf("%d\n",i);
            else if (i%j == 0)
                break;
        }
    }
}

Key improvements include:

• Changing the inner loop condition from j<i to j<=i, ensuring that when i=2, the inner loop executes at least once (as j=2 satisfies j<=i).
• Adjusting the order of conditional checks: first checking i == j, then i%j == 0. When j increments to equal i, it indicates that all previous j values failed to divide i, confirming i as prime.
• This logic better aligns with the definition of prime numbers: if a number is divisible only by 1 and itself, then as the inner loop iterates j from 2 to i, output should occur only when j==i.

Algorithm Principles and Extended Discussion

The core of prime detection lies in divisibility testing. The optimized algorithm iterates through all potential divisors (from 2 to i itself) in the inner loop. Upon finding a divisor (i%j == 0), it breaks immediately, as this indicates i is not prime. Only when the loop completes to j==i is it confirmed that no other divisors were found.

It is worth noting that this algorithm can be further optimized. For instance, the inner loop upper bound could be changed to j<=i/2 or j*j<=i, since the smallest prime factor of a composite number does not exceed its square root. However, for clarity and educational purposes, the current version is sufficiently effective.

Additionally, the article discusses the fundamental difference between the HTML tag <br> and the character \n: the former is used for line breaks in HTML structure, while the latter is a newline character in C strings that takes effect when output to the console.

Conclusion and Recommendations

This case demonstrates the critical importance of handling boundary conditions when writing loops and conditional statements. Beginners should pay special attention to loop initial values, termination conditions, and iteration steps to avoid off-by-one errors. The order of conditional checks also affects program logic flow and should be arranged according to specific requirements.

For prime number printing tasks, it is advisable to first clarify the mathematical definition of prime numbers and then design an appropriate detection algorithm. Testing should begin with edge cases, such as the smallest prime number 2, to ensure correct operation under all conditions.