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
, thenfactorial(4)
should evaluate to24
andfactorial(0)
should evaluate to1
.
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.