Solving problems with loops

Digits: % 10 and / 10

n % 10 gives the last digit of a non-negative number, and n / 10 removes it. Repeating both until n becomes 0 visits every digit, from right to left.

int n = 4521, sum = 0, reversed = 0;
while (n > 0) {
    int digit = n % 10;          /* 1, then 2, then 5, then 4 */
    sum += digit;
    reversed = reversed * 10 + digit;
    n /= 10;
}
printf("sum %d, reversed %d\n", sum, reversed);   /* sum 12, reversed 1254 */

Prime check: only up to the square root

A prime number has no divisors other than 1 and itself. If n has a divisor bigger than its square root, it also has a matching one smaller than the square root, so testing up to √n is enough. Write the condition as i * i <= n to avoid floating point (but beware overflow for n close to INT_MAX).

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;     /* found a divisor */
    }
    return 1;
}
/* is_prime(97) → 1, is_prime(91) → 0 (7 × 13) */

GCD with Euclid's algorithm

The greatest common divisor (GCD) of two numbers is the largest number that divides both. Euclid noticed that gcd(a, b) equals gcd(b, a % b), and gcd(a, 0) is a. Each step makes the numbers smaller, so the loop ends quickly, even for huge numbers. The LCM is then a / gcd(a, b) * b (divide first to reduce overflow).

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
/* gcd(84, 36): (84,36) → (36,12) → (12,0) → 12 */

Fibonacci

long long a = 0, b = 1;
for (int i = 0; i < 10; i++) {
    printf("%lld ", a);           /* 0 1 1 2 3 5 8 13 21 34 */
    long long next = a + b;
    a = b;
    b = next;
}

Counting and patterns

Other common tasks: count digits (keep dividing by 10), check an Armstrong number (153 = 1³ + 5³ + 3³), check a palindrome number (reverse and compare), and print number or star patterns with nested loops. They all reuse the same few ideas: % and /, an accumulator variable, and loop bounds.