YouTipC Exercise Example12
# C Programming Classic 100 Examples: Exercise 12 - Find Prime Numbers Between 101 and 200
In this tutorial, we will explore how to identify and print all prime numbers within a specific range (from 101 to 200) using the C programming language. This exercise is a classic problem for understanding loops, conditional statements, and algorithm optimization.
---
## Problem Description
**Goal:** Find and print all prime numbers between 101 and 200.
### What is a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, and 11 are prime numbers, whereas 4, 6, 8, and 9 are composite numbers.
### Algorithm Analysis
To determine if a number $n$ is prime:
1. **Basic Approach:** Divide $n$ by every integer from $2$ up to $n - 1$. If $n$ is divisible by any of these numbers, it is not prime.
2. **Optimized Approach:** Instead of checking up to $n - 1$, we only need to check divisors up to the square root of $n$ ($\sqrt{n}$). If a number $n$ has a divisor larger than $\sqrt{n}$, it must also have a corresponding divisor smaller than $\sqrt{n}$.
3. **Advanced Optimization ($6k \pm 1$ rule):** All primes greater than 3 can be written in the form $6k \pm 1$, where $k$ is an integer. This allows us to skip checking multiples of 2 and 3 entirely, significantly speeding up the calculation.
---
## Code Examples
Below are two different implementations. The first uses a straightforward nested loop approach, while the second uses a highly optimized helper function.
### Method 1: Standard Nested Loop Approach
This method uses a basic nested loop to check for divisors. It keeps track of the output formatting by printing a newline character after every 5 prime numbers.
```c
#include
int main()
{
int i, j;
int count = 0; // Counter to format the output (5 numbers per line)
for (i = 101; i <= 200; i++)
{
for (j = 2; j < i; j++)
{
// If i is divisible by j, it is not a prime number
if (i % j == 0)
break;
}
// If the loop finished without breaking, j will equal i, meaning i is prime
if (j >= i)
{
count++;
printf("%d ", i);
// Print a newline after every 5 prime numbers
if (count % 5 == 0)
printf("\n");
}
}
return 0;
}
```
#### Output
```text
101 103 107 109 113
127 131 137 139 149
151 157 163 167 173
179 181 191 193 197
199
```
---
### Method 2: Optimized Approach Using the $6k \pm 1$ Rule
This method modularizes the logic by creating an `isPrime` helper function. It uses the $6k \pm 1$ optimization rule to skip redundant checks, making it highly efficient for larger ranges.
```c
#include
#include
// Function: Check if a number is prime
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true; // 2 and 3 are prime
// Eliminate multiples of 2 and 3
if (num % 2 == 0 || num % 3 == 0) return false;
// Check factors up to the square root of num using 6k +/- 1
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) return false;
}
return true;
}
int main() {
printf("List of prime numbers between 101 and 200:\n");
for (int i = 101; i <= 200; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
```
#### Output
```text
List of prime numbers between 101 and 200:
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
```
---
## Code Analysis & Key Concepts
### 1. The `isPrime` Function (Method 2)
* **Base Cases:** Numbers less than or equal to 1 are not prime. Numbers 2 and 3 are explicitly marked as prime.
* **Divisibility by 2 and 3:** Any even number or multiple of 3 is immediately filtered out.
* **The Loop (`i * i <= num`):** Instead of using the `sqrt()` function from ``, we use the condition `i * i <= num`. This avoids the performance overhead of floating-point math.
* **Step Increment (`i += 6`):** By incrementing by 6, we only test potential factors of the form $6k - 1$ (represented by `i`) and $6k + 1$ (represented by `i + 2`).
### 2. Output Formatting (Method 1)
* The variable `count` keeps track of how many prime numbers have been printed.
* The condition `count % 5 == 0` ensures that the output is clean and readable by wrapping to a new line after every 5 entries.
---
## Comparison of Approaches
| Feature | Method 1 (Basic) | Method 2 (Optimized) |
| :--- | :--- | :--- |
| **Complexity** | $O(N^2)$ | $O(N \sqrt{N})$ |
| **Readability** | Simple, beginner-friendly | Structured, modular |
| **Performance** | Slow for large ranges | Extremely fast and scalable |
| **Best Used For** | Quick academic exercises | Production code / Large datasets |