Problem Solving with Loops
Putting loops to workNow that you know every loop, it is time to solve problems with them. These five programs appear in almost every C course and exam. In the lab below each one runs round by round, with the idea in plain words and a trace table — so you understand why it works, not just what it prints.
- n % 10gives the last digit
- n / 10removes the last digit
- d × d ≤ nis enough to test for primes
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
The ideas behind the lab
Exactly what you watched happen, in plain steps.
How to attack a loop problem
Most loop problems are built from a few small ideas: taking a number apart digit by digit, trying candidates one after another, and remembering something across rounds in a variable (a total, a count, a flag, the last two values). Work out the idea on paper for a small example first — then write the loop.
1. Solve a small example BY HAND (e.g. reverse 123). 2. Find what repeats → that is the loop body. 3. Decide what to remember between rounds → variables. 4. Decide when to stop → the condition. 5. Trace your loop with a table — then run it.
| Problem | Key idea | Loop | Example |
|---|---|---|---|
| Reverse / palindrome | rev = rev × 10 + n % 10; n /= 10 | while (n > 0) | 1221 → 1221 (palindrome) |
| Prime | no divisor d with d × d ≤ n | for d = 2 … √n, break | 91 = 7 × 13 → not prime |
| GCD / LCM | gcd(x, y) = gcd(y, x % y) | while (y != 0) | gcd(48, 18) = 6, lcm = 144 |
| Fibonacci | next = a + b; a = b; b = next | for i = 1 … n | 0 1 1 2 3 5 8 13 |
| Armstrong | sum of the cubes of the digits = n | while (t > 0) | 153 = 1 + 125 + 27 |
Digit tricks
- n % 10 is the last digit; n / 10 removes it.
- while (n > 0) { d = n % 10; …; n /= 10; } visits every digit, right to left.
- rev = rev * 10 + d builds a number from digits (here in reverse).
- Copy n first if you still need the original afterwards.
- Sum of digits, count of digits, reverse, palindrome, Armstrong — all use this loop.
Divisors and multiples
- d divides n when n % d == 0.
- To test for a prime, try d = 2, 3, … while d * d <= n, and break at the first divisor.
- 0 and 1 are not prime; 2 is the only even prime.
- Euclid's GCD: replace (x, y) by (y, x % y) until y is 0.
- lcm(a, b) = a / gcd × b (divide first to avoid overflow).
Building blocks
- Accumulator: sum = 0; sum += … (or product = 1; product *= …).
- Counter: count = 0; count++ when something is found.
- Flag: isPrime = 1; set it to 0 when the answer changes.
- Sliding pair: keep the last two values (a, b) for sequences like Fibonacci.
- Watch the int limits: factorials and Fibonacci numbers grow very fast — use long long.
All primes up to 30 — a loop inside a loop
Every line, explained.
#include <stdio.h>
int main(void)
{
int count = 0;
A counter for the primes found.
for (int n = 2; n <= 30; n++) {
The outer loop tries every candidate n.
int isPrime = 1;
A flag: assume n is prime.
for (int d = 2; d * d <= n; d++) {
The inner loop tests the divisors of this n.
if (n % d == 0) {
isPrime = 0;
Found a divisor: not prime.
break;
Leaves only the INNER loop — the outer loop goes on with the next n.
}
}
if (isPrime) {
printf("%d ", n);
Prints 2 3 5 7 11 13 17 19 23 29
count++;
}
}
printf("\n%d primes\n", count);
Prints 10 primes
return 0;
}
Spot the bug
Mistakes almost every beginner makes — and how to fix them.
Losing the original number
while (n > 0) { rev = rev * 10 + n % 10; n /= 10; }
if (rev == n) … // n is 0 now!
int copy = n;
while (n > 0) { rev = rev * 10 + n % 10; n /= 10; }
if (rev == copy) …
The loop destroys n. Keep a copy before the loop when you need the original later.
d * d < n instead of <=
for (d = 2; d * d < n; d++) // 25 → "prime"
for (d = 2; d * d <= n; d++)
For n = 25 the divisor 5 has 5 × 5 = 25, which < 25 skips. Squares of primes are then called prime.
Calling 1 a prime
int isPrime = 1; // also for n = 1
int isPrime = n > 1;
The loop never runs for n = 1, so the flag stays 1. A prime needs exactly two divisors: 1 is not prime.
int overflow in fast-growing results
int f = 1; for (i = 1; i <= 15; i++) f *= i; // wrong
long long f = 1; for (i = 1; i <= 15; i++) f *= i; // 1307674368000
13! is already larger than the biggest int. Factorials, powers and Fibonacci numbers need long long.
Resetting the accumulator inside the loop
for (i = 1; i <= 5; i++) {
int sum = 0;
sum += i;
}
int sum = 0;
for (i = 1; i <= 5; i++)
sum += i;
A variable created inside the body starts again every round (and is gone after the loop).
Check your understanding
Answer each question — you will see the explanation straight away.
What does 4729 % 10 give?
% 10 gives the last digit.
rev starts at 0. After processing the digits of 123 with rev = rev * 10 + n % 10, rev is?
3 → 32 → 321.
To check whether 97 is prime, up to which divisor must you test?
Test d while d * d <= 97: up to 9.
gcd(48, 18) with Euclid: (48,18) → (18,12) → (12,6) → (6,0). The gcd is?
When y becomes 0, x is the gcd: 6.
The first Fibonacci numbers are 0, 1, 1, 2, 3, 5 … What comes next?
3 + 5 = 8.
Problem Solving with Loops quiz
Test yourself: 10 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.