Week 4

Loops

Exercise 4.1

Write a program that prompts the user for an integer and prints all the prime numbers less than or equal to that integer.

For example, if the user enters

20

the program should print

2
3
5
7
11
13
17
19

and if the user enters

1

the program should print nothing.

Solution

Here is one possible solution.

#include <iostream>

using namespace std;

int main() {
    int max;

    cout << "Enter maximum number: ";
    cin >> max;

    for (int n = 2; n <= max; ++n) {
        bool prime = true;

        for (int d = 2; d < n; ++d) {
            if (n % d == 0) {
                prime = false;
                break;
            }
        }

        if (prime) {
            cout << n << "\n";
        }
    }

    return 0;
}

Random number generation

To generate random numbers, we can use the random library as follows.

#include <iostream>
#include <random>

using namespace std;

int main() {
    random_device rd;
    default_random_engine gen(rd());

    uniform_int_distribution<int> dist_int(-5, 10);

    for (int i = 0; i < 5; ++i) {
        cout << dist_int(gen) << '\n';
    }

    uniform_real_distribution<double> dist_real(0, 5);

    for (int i = 0; i < 5; ++i) {
        cout << dist_real(gen) << '\n';
    }

    return 0;
}

The lines

    random_device rd;
    default_random_engine gen(rd());

are used to initialize and seed the random number generator.

To generate random integers in a specified range, we initialize a uniform_int_distribution<int>; to generate real numbers, we initialize a uniform_real_distribution<double>. Note that

    uniform_int_distribution<int> dist(a, b)

will generate random integers in $\set{a, a+1, \dots, b}$ (i.e., including $b$) and

    uniform_real_distribution<double> dist(a, b)

will generate random real numbers in $[a, b)$ (i.e., excluding $b$).

To invoke the generator, we write

    dist(gen)

where dist is the name of the distribution and gen is the name of the generator.

Functions

Exercise 4.2

Write a function that computes the factorial of a nonnegative integer. Recall that the factorial of a nonnegative integer $n$ is $n! = n \cdot (n-1) \cdot (n-2) \cdot \cdots \cdot 2 \cdot 1$ and that $0! = 1$.

For example, if the function is named factorial, then factorial(4) should evaluate to 24 and factorial(0) should evaluate to 1.

Solution

Here is one possible solution, using iteration.

int factorial(int n) {
    int product = 1;

    for (int i = 1; i <= n; ++i) {
        product *= i;
    }

    return product;
}

Alternative solution

Here is another possible solution, using recursion.

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

The function in Exercise 4.2 could be used to compute binomial coefficients. Recall that the binomial coefficient $n \choose k$ is equal to $\frac{n!}{(n-k)! k!}$ (where $n$ and $k$ are integers with $0 \leq k \leq n$). For instance, we could write the function

int binomial(int n, int k) {
    return factorial(n) / (factorial(n-k) * factorial(k));
}

which computes the binomial coefficient of its arguments.