Program Decomposition

So far each function had one small job, and the problem told you what it was. Longer problems don't: they say what the answer is, and you decide how to split the work. That splitting is called decomposition, and it is the most useful habit you can pick up this week.

Top-down: write main first

Here is a problem:

A number is a double prime if it is prime and the sum of its digits is prime too. You are given n numbers (1 ≤ n ≤ 1000, each between 1 and 10⁶). Print the double primes in the order they are given, and then how many there were.

Read the statement and underline each thing that has to be checked or computed: is it prime, the sum of its digits, is it a double prime. Each becomes a function. Then write main as if those functions already existed:

main is now short enough to check at a glance. What is left are three small problems, each of which can be written and tested alone.

The whole program:

For the numbers 23 13 29 31 47 89 10 it prints 23 29 47 89 and 4. isDoublePrime is just the two helpers combined — a function built from functions. Step through one number and watch main hand the work out:

Is 23 a double prime? main asks, the helpers answer

C++

1#include <bits/stdc++.h>

2using namespace std;

4bool isPrime(int n) {

5 if (n < 2) {

6 return false;

7 }

8 for (int d = 2; d * d <= n; d++) {

9 if (n % d == 0) {

10 return false;

11 }

12 }

13 return true;

14}

16int digitSum(int n) {

17 int s = 0;

18 while (n > 0) {

19 s += n % 10;

20 n /= 10;

21 }

22 return s;

23}

25int main() {

26 ios_base::sync_with_stdio(false);

27 cin.tie(NULL);

29 int x = 23;

30 if (isPrime(x) && isPrime(digitSum(x))) {

31 cout << x << " is a double prime\n";

32 }

33 return 0;

34}

Start in main()

сатр 25

Every C++ program starts in main().

стеки даъватҳо

main()

x—n—d—s—

1 / 38

Helper	Does	Seen in
`bool isPrime(int n)`	tries divisors while `d * d <= n`	this lesson
`int digitSum(int n)`	`n % 10` and `n /= 10` in a loop	this lesson
`long long gcd(long long a, long long b)`	Euclid's loop	this lesson
`int countDivisors(int n)`	divisor pairs up to √n	this lesson
`bool isPalindrome(const string &s)`	compares the two ends, walking inwards	Parameters and Scope
`vector<int> readVector(int n)`	reads n numbers	Parameters and Scope

Top-down: write main first

Practice: Program Decomposition

Testing whether a number is prime

The greatest common divisor

A small toolbox

A list of commands

What makes a good function

Check your understanding