SyntaxPilot
Courses/C++ Coding Questions/Lesson 3
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 3 of 30

Number questions II

prime check (why up to √n, i * i overflow)primes up to n with a sieve (vector<bool>)GCD and LCM (Euclid, std::gcd, lcm overflow)

These are the notes for C++ Coding Questions, episode 3, placement practice for people who finished the SyntaxPilot C++ course. Number questions part two: checking if a number is prime (fast and overflow-safe), counting all primes up to 50 million with the sieve of Eratosthenes, and GCD and LCM with Euclid's algorithm.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64, 32-bit int, 8 MB stack), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In maths / C++
12 chairs in a full rectangle: 1 × 12, 2 × 6, 3 × 4 composite: has divisors other than 1 and itself
13 chairs: only one long line, 1 × 13 prime: exactly two divisors, 1 and itself
3 × 4 is 4 × 3 turned around divisors come in pairs; the smaller one is at most √n
a 24 × 36 floor, the biggest square tile without cutting: 12 × 12 GCD (greatest common divisor) = 12
buses every 12 and 18 minutes leave together again after 36 LCM (least common multiple) = 36
12 × 18 = 216 = 6 × 36 a × b = GCD × LCM

1 is not a prime: a prime needs exactly two different divisors.

Q1: Is n prime?

Problem. Read integers n (up to 2,147,483,647) and say for each whether it is prime.

Input Output
2 prime (the only even prime)
9 not (3 × 3)
13 prime
1 not
2147483647 prime (2³¹ − 1, a famous Mersenne prime)

The obvious attempt: try every divisor from 2 to n − 1

#include <iostream>
using namespace std;

bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    while (cin >> n)
        cout << n << (isPrime(n) ? " is prime\n" : " is not prime\n");
    return 0;
}

Input 2 9 13 1:

2 is prime
9 is not prime
13 is prime
1 is prime

Bug 1: for n = 1 the loop never runs, so the function falls through to return true.

Input 2147483647 2147483629 2147483587 2147483579:

Time Limit Exceeded (stopped after 8 seconds)

Bug 2: each big prime tries about 2 billion divisors; four of them is about 8 billion steps.

Fix: n < 2 is not prime, and stop at √n

If n = a × b with a ≤ b, then a × a ≤ n, so a ≤ √n. If nothing up to √n divides n, nothing above it can either. For 2,147,483,647 that is about 46,341 tries instead of 2 billion.

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    while (cin >> n)
        cout << n << (isPrime(n) ? " is prime\n" : " is not prime\n");
    return 0;
}

Input 2 9 13 1 25:

2 is prime
9 is not prime
13 is prime
1 is not prime
25 is not prime

Input 2147483647:

2147483647 is not prime

Wrong! At i = 46340, i * i = 2,147,395,600 ≤ n, so the loop continues. At i = 46341, i * i = 2,147,488,281, which is more than INT_MAX: signed overflow, undefined behaviour. In this build the loop went far past √n and found a "divisor", giving a wrong answer (and taking about 3 seconds).

Fix: divide instead of multiply: i <= n / i

The same test, but no value ever gets bigger than n. (Using long long i also works.)

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    while (cin >> n)
        cout << n << (isPrime(n) ? " is prime\n" : " is not prime\n");
    return 0;
}

Input 1 2 25 97 2147483647 2147483629 2147483587 2147483579:

1 is not prime
2 is prime
25 is not prime
97 is prime
2147483647 is prime
2147483629 is prime
2147483587 is prime
2147483579 is prime

Complexity: O(√n) time per number, O(1) space.

Q2: Count the primes up to n

Problem. Read n (up to 50,000,000) and print how many primes are ≤ n.

n primes ≤ n
1 0
30 10 (2 3 5 7 11 13 17 19 23 29)
100 25
10,000,000 664,579
50,000,000 3,001,134

The obvious attempt: call isPrime for every number

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    int count = 0;
    for (int x = 2; x <= n; x++)
        if (isPrime(x)) count++;
    cout << "primes up to " << n << ": " << count << "\n";
    return 0;
}

Input 100:

primes up to 100: 25

Input 50000000:

Time Limit Exceeded (stopped after 8 seconds)

Every number is checked from scratch: about n × √n work in the worst case.

The sieve of Eratosthenes

Write the numbers 2 to n. The first unmarked number, 2, is prime: cross out all its multiples. The next unmarked number, 3, is prime: cross out its multiples, starting at 3 × 3 = 9 (smaller multiples like 6 were already crossed out by smaller primes). Repeat. Whatever is never crossed out is prime. No division at all.

Attempt: a big local bool array

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool composite[50000001] = {};
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (composite[i]) continue;
        count++;
        for (long long j = (long long)i * i; j <= n; j += i)
            composite[j] = true;
    }
    cout << "primes up to " << n << ": " << count << "\n";
    return 0;
}

Input 100:

Runtime Error (SIGSEGV): the program crashed, nothing was printed

Runtime Error (SIGSEGV), a segmentation fault, even for n = 100. Why: a variable declared inside a function lives on the stack, a small memory area for function calls (8 MB here). bool composite[50000001] needs 50 MB, so creating it runs off the end of the stack and the operating system kills the program.

Fix: vector<bool> (memory from the heap)

A vector keeps its elements on the heap, the large pool of free memory. vector<bool> is special: it stores each value in one bit, so 50 million flags take about 6 MB. Note j is a long long, so i * i cannot overflow.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> composite(n + 1, false);
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (composite[i]) continue;
        count++;
        for (long long j = (long long)i * i; j <= n; j += i)
            composite[j] = true;
    }
    cout << "primes up to " << n << ": " << count << "\n";
    return 0;
}

Input 100:

primes up to 100: 25

Input 1:

primes up to 1: 0

Input 50000000:

primes up to 50000000: 3001134

About half a second. Complexity: O(n log log n) time (almost linear), O(n) space.

Other fixes for the crash: make the array static or global (then it is not on the stack), but its size is fixed at compile time. vector sizes itself to n.

Q3: GCD and LCM

Problem. Read pairs a b (0 to 2,147,483,647) and print their GCD and LCM.

a b GCD LCM
24 36 12 72
12 18 6 36
4 6 2 12
0 5 5 (every number divides 0) 0
100000 99999 1 9,999,900,000 (bigger than an int)

The obvious GCD: count down from min(a, b)

#include <iostream>
#include <algorithm>
using namespace std;

int gcdSlow(int a, int b) {
    for (int d = min(a, b); d >= 1; d--)
        if (a % d == 0 && b % d == 0) return d;
    return 1;
}

int main() {
    int a, b;
    while (cin >> a >> b)
        cout << "gcd(" << a << ", " << b << ") = " << gcdSlow(a, b) << "\n";
    return 0;
}

Input 24 36 / 17 5 / 0 5:

gcd(24, 36) = 12
gcd(17, 5) = 1
gcd(0, 5) = 1

gcd(0, 5) should be 5: the loop starts at 0 and never runs.

Input 2147483647 2147483629 / 2147483587 2147483579 / 2147483563 2147483647 / 2147483629 2147483579:

Time Limit Exceeded (stopped after 8 seconds)

For big numbers with no common factor, it counts down about 2 billion times.

Euclid's algorithm

Any number that divides a and b also divides a % b, so gcd(a, b) = gcd(b, a % b). Repeat until b is 0; then the answer is a.

  • gcd(36, 24) → gcd(24, 12) → gcd(12, 0) = 12
  • gcd(0, 5) → gcd(5, 0) = 5

The numbers shrink at least by half every two steps, so it takes O(log min(a, b)) steps: at most about 45 for ints.

#include <iostream>
using namespace std;

int gcdE(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    while (cin >> a >> b)
        cout << "gcd(" << a << ", " << b << ") = " << gcdE(a, b) << "\n";
    return 0;
}

Input 24 36 / 17 5 / 0 5:

gcd(24, 36) = 12
gcd(17, 5) = 1
gcd(0, 5) = 5

Input 2147483647 2147483629 / 2147483587 2147483579 / 2147483563 2147483647 / 2147483629 2147483579:

gcd(2147483647, 2147483629) = 1
gcd(2147483587, 2147483579) = 1
gcd(2147483563, 2147483647) = 1
gcd(2147483629, 2147483579) = 1

The obvious LCM: a * b / g in int

#include <iostream>
using namespace std;

int gcdE(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int g = gcdE(a, b);
        int l = a * b / g;
        cout << "gcd " << g << ", lcm " << l << "\n";
    }
    return 0;
}

Input 4 6 / 12 18 / 100000 99999:

gcd 2, lcm 12
gcd 6, lcm 36
gcd 1, lcm 1409965408

The last LCM should be 9,999,900,000. Why: a * b is almost 10 billion, far past INT_MAX, so it overflowed before the division.

Fix: long long, and divide first: a / g * b

a / g is exact (g divides a), and the huge product a * b is never built. If both numbers are 0, g is 0 and dividing by zero is undefined behaviour, so the LCM is defined as 0 in that case.

#include <iostream>
using namespace std;

long long gcdE(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long a, b;
    while (cin >> a >> b) {
        long long g = gcdE(a, b);
        long long l = (g == 0) ? 0 : a / g * b;
        cout << "gcd " << g << ", lcm " << l << "\n";
    }
    return 0;
}

Input 4 6 / 12 18 / 100000 99999 / 0 5:

gcd 2, lcm 12
gcd 6, lcm 36
gcd 1, lcm 9999900000
gcd 5, lcm 0

The standard library: std::gcd and std::lcm (C++17, <numeric>)

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    long long a, b;
    while (cin >> a >> b)
        cout << "gcd " << gcd(a, b) << ", lcm " << lcm(a, b) << "\n";
    return 0;
}

Input 4 6 / 12 18 / 100000 99999 / 0 5:

gcd 2, lcm 12
gcd 6, lcm 36
gcd 1, lcm 9999900000
gcd 5, lcm 0

In a contest, use the library. In an interview, know Euclid underneath. (std::lcm can still overflow if the answer doesn't fit in the type you pass, so pass long long.)

Complexity summary

Program Time Extra space
prime check, 2 to n − 1 O(n) O(1)
prime check, up to √n O(√n) O(1)
count primes, isPrime for each O(n √n) O(1)
count primes, sieve O(n log log n) O(n)
GCD counting down O(min(a, b)) O(1)
GCD Euclid, LCM = a / g × b O(log min(a, b)) O(1)

The sieve trades memory for speed: O(n) memory to make counting almost linear.

Common mistakes (and the real results)

Mistake What you see Why Fix
no n < 2 check 1 is prime the loop never runs if (n < 2) return false;
divisors up to n − 1 Time Limit Exceeded ~2 billion tries per big prime stop at √n
i * i <= n with int i 2147483647 is not prime i * i overflows (UB) i <= n / i
isPrime for every number up to 5 × 10⁷ Time Limit Exceeded n × √n work sieve
bool composite[50000001]; inside main Runtime Error (SIGSEGV) 50 MB on an 8 MB stack vector<bool>(n + 1)
int j = i * i in the sieve UB for big i overflow long long j
GCD counting down from min(a, b) gcd(0, 5) = 1, TLE wrong start, O(min) steps Euclid
int l = a * b / g; lcm 1409965408 a * b overflows long long, a / g * b

Your turn: count the divisors (solution)

Every i up to √n that divides n gives a pair: i and n / i. For a perfect square, i == n / i once (6 × 6 = 36): count it only once.

#include <iostream>
using namespace std;

int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i <= n / i; i++) {   // i <= sqrt(n), no overflow
        if (n % i == 0) {
            count++;                     // i
            if (i != n / i) count++;     // its partner n / i, unless i * i == n
        }
    }
    return count;
}

int main() {
    int n;
    while (cin >> n)
        cout << n << " has " << countDivisors(n) << " divisors\n";
    return 0;
}

Input 12 / 13 / 36 / 1 / 2147483647 / 735134400:

12 has 6 divisors
13 has 2 divisors
36 has 9 divisors
1 has 1 divisors
2147483647 has 2 divisors
735134400 has 1344 divisors

Time O(√n), space O(1).

Practice questions (with solutions)

1. All prime factors of n (60 → 2 2 3 5). Divide out each p as long as it divides n; whatever is left above 1 at the end is a prime.

Solution
#include <iostream>
using namespace std;

int main() {
    long long n;
    while (cin >> n) {
        cout << n << ":";
        for (long long p = 2; p <= n / p; p++)
            while (n % p == 0) {      // take out every copy of p
                cout << " " << p;
                n /= p;
            }
        if (n > 1) cout << " " << n;  // what is left is a prime
        cout << "\n";
    }
    return 0;
}

Input 60 / 97 / 1 / 1024 / 9999999967:

60: 2 2 3 5
97: 97
1:
1024: 2 2 2 2 2 2 2 2 2 2
9999999967: 9999999967

2. GCD of a whole list. gcd(a, b, c) = gcd(gcd(a, b), c), and gcd(0, x) = x.

Solution
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int k;
    cin >> k;
    vector<long long> v(k);
    for (auto &x : v) cin >> x;
    long long g = 0;                  // gcd(0, x) = x, so 0 is a safe start
    for (long long x : v) g = gcd(g, x);
    cout << "gcd of the list: " << g << "\n";
    return 0;
}

Input 4 / 24 36 60 84:

gcd of the list: 12

3. Twin primes up to n (pairs of primes that differ by 2), with a sieve.

Solution
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> composite(n + 1, false);
    for (int i = 2; (long long)i * i <= n; i++)
        if (!composite[i])
            for (long long j = (long long)i * i; j <= n; j += i)
                composite[j] = true;
    for (int p = 2; p + 2 <= n; p++)
        if (!composite[p] && !composite[p + 2])
            cout << p << " " << p + 2 << "\n";
    return 0;
}

Input 50:

3 5
5 7
11 13
17 19
29 31
41 43

Mini project: a number toolkit

For each pair: prime or not, GCD, LCM, and whether they are coprime (GCD 1).

#include <iostream>
#include <numeric>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    long long a, b;
    while (cin >> a >> b) {
        cout << a << " and " << b << ": ";
        cout << (isPrime(a) ? "prime" : "not prime") << ", " << (isPrime(b) ? "prime" : "not prime");
        long long g = gcd(a, b);
        cout << ", gcd " << g << ", lcm " << lcm(a, b);
        cout << (g == 1 ? ", coprime\n" : "\n");
    }
    return 0;
}

Input 12 18 / 13 17 / 2147483647 2147483629:

12 and 18: not prime, not prime, gcd 6, lcm 36
13 and 17: prime, prime, gcd 1, lcm 221, coprime
2147483647 and 2147483629: prime, prime, gcd 1, lcm 4611685975477714963, coprime

Quick quiz

#include <iostream>
using namespace std;

int main() {
    int a = 48, b = 18, steps = 0;
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
        steps++;
    }
    cout << a << " " << steps << "\n";
    return 0;
}

(A) 6 3 (B) 6 2 (C) 18 3 (D) 3 6

Answer

(A) 6 3. (48, 18) → (18, 12) → (12, 6) → (6, 0): GCD 6 after 3 steps.

Output:

6 3

Interview questions

  1. Why check divisors only up to √n? Divisors come in pairs a × b = n; the smaller one is at most √n.
  2. Is 1 prime? Is 2? 1 is not (one divisor); 2 is the only even prime.
  3. What's wrong with i * i <= n? It overflows near INT_MAX; use i <= n / i or long long.
  4. Explain the sieve of Eratosthenes and its complexity. Cross out multiples of each prime starting at p²; O(n log log n) time, O(n) space.
  5. Why start crossing out at p × p? Smaller multiples k × p (k < p) were already crossed out by the smaller prime factor of k.
  6. Stack vs heap? Local variables live on the small stack (a few MB); new and containers like vector use the large heap.
  7. Explain Euclid's algorithm. gcd(a, b) = gcd(b, a % b) until b = 0; O(log) steps.
  8. Relation between GCD and LCM? a × b = gcd × lcm; compute lcm = a / gcd × b to avoid overflow.
  9. What are std::gcd and std::lcm? C++17 functions in <numeric>.

Glossary

Term Meaning Example
Divisor A number that divides another with no remainder 3 divides 12
Prime A number with exactly two divisors, 1 and itself 2, 13, 2147483647
Composite A number above 1 that is not prime 12 = 3 × 4
√n (square root) The number that times itself gives n √36 = 6
Divisor pair Two divisors whose product is n 3 and 4 for 12
Signed overflow A signed result too big for its type: undefined behaviour 46341 * 46341 in an int
INT_MAX The largest int: 2,147,483,647 <climits>
Sieve of Eratosthenes Find all primes up to n by crossing out multiples primes up to 50 million
Stack Small memory area for local variables and calls about 8 MB here
Heap Large pool of free memory for dynamic data where vector stores elements
Segmentation fault (SIGSEGV) The OS stops a program that touched memory it may not use a 50 MB local array
vector<bool> A vector that stores each bool in one bit vector<bool> composite(n + 1)
GCD Greatest common divisor: the biggest number dividing both gcd(24, 36) = 12
LCM Least common multiple: the smallest number both divide lcm(12, 18) = 36
Coprime Two numbers whose GCD is 1 13 and 17
Euclid's algorithm gcd(a, b) = gcd(b, a % b) until b = 0 (48, 18) → 6
std::gcd, std::lcm Library GCD and LCM (C++17) #include <numeric>
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here
O(√n) Work grows like the square root of n 46,341 steps for 2 billion
O(n log log n) Almost linear the sieve
O(log n) Grows very slowly Euclid
Prime factorisation Writing n as a product of primes 60 = 2 × 2 × 3 × 5

Summary

  • A prime has exactly two divisors; 1 is not prime. Test divisors only up to √n, written i <= n / i so nothing overflows.
  • To count many primes, use the sieve of Eratosthenes: cross out multiples from p × p, O(n log log n).
  • Big arrays go in a vector (the heap), not a local array (the stack): a 50 MB local array crashes with SIGSEGV.
  • Euclid: gcd(a, b) = gcd(b, a % b), O(log); gcd(0, n) = n.
  • LCM = a / gcd × b, in long long: a * b overflows an int. C++17 has std::gcd and std::lcm.

Next episode: Bits and number bases: decimal to binary with bitset, counting set bits, and the one-line power-of-two check n & (n - 1).