C programming language → Nested Loops in C

Nested Loops in C

A nested loop is a loop inside the body of another loop. For every pass of the outer loop, the inner loop runs completely. Nested loops are used for tables, star patterns, checking all pairs of numbers and walking through matrices.

How a loop inside a loop works

If the outer loop makes n passes and the inner one m, the body of the inner loop is executed n · m times. The outer counter i changes slowly (like the hour hand), the inner counter j changes fast (like the minute hand):

#include <stdio.h>

int main(void) {
    for (int i = 1; i <= 3; i++)          /* outer loop */
        for (int j = 1; j <= 2; j++)      /* inner loop restarts for every i */
            printf("i=%d j=%d\n", i, j);
    return 0;
}

Example 1: numbers 1 to 100 in 10 rows and 10 columns

The outer loop counts rows, the inner one counts columns. The number in row i and column j is (i − 1) · 10 + j; to print one number we use printf("%4d", number).

#include <stdio.h>

int main(void) {
    for (int i = 1; i <= 10; i++) {          /* row */
        for (int j = 1; j <= 10; j++) {      /* column */
            int number = (i - 1) * 10 + j;
            printf("%4d", number);           /* 4 characters per number */
        }
        printf("\n");                        /* end of the row */
    }
    return 0;
}

The same task can be solved with a single loop (new line after every tenth number) – see Loops in C/C++ – examples.

Example 2: star patterns

The key question for every pattern is: how many characters are in row i? The inner loop depends on i.

PatternRow i (1 to n) contains
rectangle n × mm stars
trianglei stars
pyramidn − i spaces, then 2·i − 1 stars
 
#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i; j++)     /* spaces */
            printf(" ");
        for (int j = 1; j <= 2 * i - 1; j++) /* stars: 1, 3, 5, ... */
            printf("*");
        printf("\n");
    }
    return 0;
}

Example 3: all pairs

To check every pair exactly once, the inner loop starts at i + 1. The program prints all pairs of array elements whose sum is k:

#include <stdio.h>

int main(void) {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)      /* only pairs with i < j */
            if (a[i] + a[j] == k) {
                printf("%d + %d\n", a[i], a[j]);
                count++;
            }
    printf("Pairs: %d\n", count);
    return 0;
}

There are n·(n−1)/2 pairs. For n = 1000 that is half a million checks (fast); for n = 100 000 it is 5 billion, which is too slow for competitions.

break in the inner loop: prime numbers

break leaves only the loop it is written in. Here it stops searching for divisors, and the outer loop continues with the next number:

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    for (int x = 2; x <= n; x++) {
        int prime = 1;
        for (int d = 2; d * d <= x; d++)     /* divisors up to the square root */
            if (x % d == 0) {
                prime = 0;
                break;                        /* leaves only the loop over d */
            }
        if (prime)
            printf("%d ", x);
    }
    printf("\n");
    return 0;
}

Exercises

Try to solve each exercise first; then open the hint and the solution.

EXERCISE 01Level: easy

Multiplication table

Read n and print the multiplication table n × n; every number takes 4 characters (%4d).

Example

Input

3

Output

   1   2   3
   2   4   6
   3   6   9
EXERCISE 02Level: easy

Number triangle

Read n. Row i contains the numbers from 1 to i, separated by spaces.

Example

Input

4

Output

1
1 2
1 2 3
1 2 3 4
Common mistakes and tips
  • Use a different counter for the inner loop (j), never the outer one (i).
  • Declare the inner counter in the inner for, so it starts from the beginning for every row.
  • printf("\n") for the end of a row goes after the inner loop, inside the outer one.
  • Two nested loops up to n make about n² steps; a computer does roughly 108 simple steps per second.