A function is a named sequence of instructions that performs a specific task. Once defined, it can be
called in your program wherever that particular task should be performed.
A function can receive zero or more values. The values sent in are called arguments; the variables inside
the function that receive them are called parameters. For example, here is a function total with three
parameters named a, b, and c, which returns their sum:
int total(int a, int b, int c)
{
return a + b + c;
}
To call a function, you supply its arguments. To compute the sum of 500, 600, and 700, you write
total(500, 600, 700) — those three values are the arguments.
#include <iostream>
using namespace std;
// Function prototype
int total(int a, int b, int c);
int main()
{
// We call it with the actual arguments 1, 20, 300,
// and save the result in a variable x
int x = total(1, 20, 300);
cout << x << endl; // Prints 321
return 0;
}
int total(int a, int b, int c)
{
return a + b + c;
}
// Returns the maximum of two arguments
int max2(int a, int b)
{
if (a > b)
return a;
else
return b;
}
A return value can be used anywhere a value can — including as an argument to another call. So you can find
the maximum of three integers like this:
max2( max2(135, 8763), 500 ) // returns 8763
The inner call runs first, produces 8763, and that result becomes the first argument of the outer call.
By the end of this lab your program will contain seven functions. That is enough that a little organization
starts to matter, so let’s establish how we will work.
C++ reads your file from top to bottom, and you must place either the function definition or the function
prototype ahead of every call to that function. If you rely on definitions alone, then order matters: every
function has to appear above the first place it is used, which strands main at the bottom of the file.
The alternative is a function prototype — the function’s header followed by a semicolon, with no body:
bool isDivisibleBy(int n, int d); // prototype: no body, ends with ;
A prototype tells the compiler everything it needs in order to check a call: the function’s name, what it
takes, and what it returns. With prototypes at the top, the definitions can appear in any order you like:
#include <iostream>
using namespace std;
// Function prototypes
bool isDivisibleBy(int n, int d);
bool isPrime(int n);
int main()
{
// can call both functions here, even though
// neither has been defined yet
return 0;
}
bool isDivisibleBy(int n, int d)
{
...
}
bool isPrime(int n)
{
...
}
Use this layout for numbers.cpp from the very beginning, and add a prototype each time you add a function.
Notice what the prototype buys you: the definitions at the bottom are in the opposite order from the
calls, and it does not matter at all.
A variable declared inside a function exists only inside that function. It is created when the function is
called and destroyed when the function returns, and no other function can see it. This is called the
variable’s scope. A function’s parameters are local variables too — they follow exactly the same rule.
That is a feature, not a restriction. It means you can use a loop counter i inside isPrime without
worrying in the slightest about whether some other function also uses a variable called i. Each function
gets its own private workspace, which is what lets you write and debug them one at a time.
Avoid global variables — variables declared outside of all functions. A global can be modified from
anywhere, which means that when its value is wrong, the suspect list is your entire program. A global
constant is a different matter and is perfectly good practice, because its value can never change:
const int QUIT = 0; // fine — a global constant
const double PAY_RATE = 22.55;
You will want one of these in Task G.
Here is how we are going to build the program, and it is worth doing in this order.
A stub is a dummy function that stands in for one you have not written yet. It has the correct header, and
its body simply displays a message confirming that it was called — printing the values it received — plus a
placeholder return value if the function needs one:
bool isPrime(int n)
{
cout << " [stub] isPrime called with n = " << n << endl;
return false;
}
A stub confirms two things: that the function is being called when you expect it to be, and that sensible
values are arriving in its parameters. It also keeps your program compiling and running at every moment,
instead of leaving you to write two hundred lines and then meet forty compiler errors at once.
A driver is a temporary main written for no purpose other than exercising the function you are currently
working on:
int main()
{
cout << isDivisibleBy(100, 25) << endl; // expect 1
cout << isDivisibleBy(35, 17) << endl; // expect 0
cout << isDivisibleBy(7, 7) << endl; // expect 1
return 0;
}
Note the comments recording what each call should print. Write the expected answer down before you run
the driver — a test you check after seeing the output is not much of a test.
Every task below is one turn of this cycle: write the prototype, stub it, write a driver, then implement it
for real.
In a program numbers.cpp, define a function
bool isDivisibleBy(int n, int d);
If n is divisible by d, the function should return true, otherwise return false.
isDivisibleBy(100, 25) == true
isDivisibleBy(35, 17) == false
Hint: the modulo operator % computes the remainder of a division. 37 % 10 is 7. What is the
remainder when one number divides another evenly? You have seen this exact shape in lecture as isEven,
which tests number % 2 == 0; your function is the same idea with the 2 promoted to a parameter.
boolisDivisibleBy is a Boolean function — its whole job is to answer one yes-or-no question. Most of the
functions in this lab are Boolean functions, and they are worth naming as a category because of how they read
at the call site:
if (isDivisibleBy(n, 3)) // "if n is divisible by 3"
cout << "divisible by three" << endl;
Note that we wrote if (isDivisibleBy(n, 3)) and not if (isDivisibleBy(n, 3) == true). The comparison with
true is redundant — the call already is a bool. Beginning programmers write the longer form constantly;
train yourself out of it now.
Write a driver main that tests your function on several pairs of numbers, including a few where you have to
think for a second about what the right answer is. What should isDivisibleBy(0, 5) be? What about
isDivisibleBy(5, 0)?
A prime number is an integer greater than or equal to 2 that is only divisible by 1 and by itself.
The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 …
N is a prime if and only if it is not divisible evenly by any of the numbers from 2 to N−1.
In the same program, add a function
bool isPrime(int n);
that returns true if n is a prime, otherwise false.
Call isDivisibleBy from inside isPrime rather than writing another % test. You already wrote that
function and you already tested it — use it. This is the habit the rest of the lab is built on.
Update your driver to test the new function. Make sure it gets the awkward cases right: isPrime(2) is
true, isPrime(1) is false, and so are isPrime(0) and isPrime(-7).
Add a function
int nextPrime(int n);
that returns the smallest prime greater than n.
nextPrime(14) == 17
nextPrime(17) == 19
Note the second example: nextPrime(17) is 19, not 17. “Greater than” is strict.
Again, do not test primality by hand here — you have isPrime.
Add a function
int countPrimes(int a, int b);
that returns the number of primes in the interval a ≤ x ≤ b.
countPrimes(10, 20) == 4 // 11, 13, 17, 19
Now add a second function with the same name but only one parameter, which counts all the primes from 2
up to and including b:
int countPrimes(int b);
countPrimes(20) == 8 // 2, 3, 5, 7, 11, 13, 17, 19
Two functions in the same program may share a name, as long as the compiler can tell the calls apart by their
arguments. This is called overloading. When you write countPrimes(20), the compiler sees one integer
argument, finds the one-parameter version, and calls that one; countPrimes(10, 20) selects the other.
What the compiler uses to choose is the function’s signature — its name plus the data types of its
parameters, in order. The return type is not part of the signature, so two functions that differ only in
what they return will not compile.
Overloading is for operations that are conceptually the same thing with different inputs, which is the case
here: both functions count primes. It is not a license to give unrelated functions the same name because you
have run out of ideas.
Implement the one-parameter version by calling the two-parameter version. It should be one line.
In the next lab we will meet default arguments, which are a second way to let a caller supply fewer
values than the full parameter list. Keep this task in mind — the two features solve overlapping problems,
and part of learning C++ is developing a sense for which one a given situation wants.
A prime number N is called a twin prime if either N−2 or N+2 (or both) is also a prime.
For example, 17 is a twin prime, because 17+2 = 19 is also a prime.
The first few twin primes are: 3, 5, 7, 11, 13, 17, 19, 29, 31 …
Add a function
bool isTwinPrime(int n);
that determines whether or not its argument is a twin prime. By now the pattern should be obvious: this
function should be short, because isPrime already does the hard part.
Add two more functions:
int nextTwinPrime(int n);
int largestTwinPrime(int a, int b);
nextTwinPrime returns the smallest twin prime greater than n.
largestTwinPrime returns the largest twin prime in the range a ≤ N ≤ b, or -1 if the range
contains no twin primes.
largestTwinPrime(5, 18) == 17
largestTwinPrime(1, 31) == 31
largestTwinPrime(14, 16) == -1
Returning -1 to mean “there isn’t one” is a common convention for functions that return a count or an index,
because -1 is not a valid answer under normal circumstances. It works, but notice that it puts a burden on
whoever calls the function: they have to remember to check for it. Later in the course we will see cleaner
ways to report that an answer does not exist.
You now have seven working functions and a main full of test calls. Let’s turn the program into something a
person could actually use.
Replace your driver main with a menu-driven loop: display a list of options, read the user’s choice, ask
for whatever numbers that option needs, call the appropriate function, print the answer, and then show the
menu again. The program keeps going until the user chooses to quit.
$ ./numbers
===== Prime Number Tools =====
1. Is a divisible by b?
2. Is n a prime?
3. Next prime after n
4. Count primes in range
5. Is n a twin prime?
6. Next twin prime after n
7. Largest twin prime in range
0. Quit
Choice: 2
Enter n: 91
91 is not a prime.
===== Prime Number Tools =====
1. Is a divisible by b?
...
0. Quit
Choice: 3
Enter n: 91
The next prime after 91 is 97.
===== Prime Number Tools =====
...
Choice: 0
Goodbye!
Structure it the way the Health Club Membership program does in lecture:
void displayMenu(); — displays the menu and nothing else. This is your first void function in theint getChoice(); — displays the prompt, reads the user’s choice, and validates it before returning.main can simply trust the value it gets back and nevermain handles only the loop and the dispatching. A switch on the choice is a natural fit.Use global constants for the menu bounds rather than writing bare numbers into the conditions:
const int QUIT = 0;
const int MAX_CHOICE = 7;
This is the last state of numbers.cpp, and it is the version you submit.
Your isPrime tests every divisor from 2 up to n−1. That is far more work than necessary.
If n has a divisor larger than its square root, then it must also have one smaller than its square root
(their product is n). So it is enough to test divisors up to √n — everything past that point is
guaranteed to tell you nothing new.
Write a second version of the function under a different name:
bool isPrimeFast(int n);
The cleanest way to express the stopping condition avoids floating-point numbers entirely: keep looping while
d * d <= n.
Then convince yourself it is actually faster and actually correct:
isPrime and isPrimeFast on every value from −10 tocountPrimes on a large range, say countPrimes(2, 200000), and time both versions with thetime command in the terminal:$ time ./numbers
Report what you observe in a comment at the top of your program.
Unlike most labs in this course, this lab builds one single program, numbers.cpp, which grows with each
task. Submit the final version, containing all of your functions and the menu-driven main from Task G.
Your program should start with a comment that contains your name and a short program description, for example:
/*
Author: your name
Course: CSCI-135
Instructor: their name
Assignment: Lab2
Here, briefly, at least in one or a few sentences
describe what the program does.
*/