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
staticor global (then it is not on the stack), but its size is fixed at compile time.vectorsizes itself ton.
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
- Why check divisors only up to √n? Divisors come in pairs
a × b = n; the smaller one is at most √n. - Is 1 prime? Is 2? 1 is not (one divisor); 2 is the only even prime.
- What's wrong with
i * i <= n? It overflows nearINT_MAX; usei <= n / iorlong long. - 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.
- Why start crossing out at p × p? Smaller multiples k × p (k < p) were already crossed out by the smaller prime factor of k.
- Stack vs heap? Local variables live on the small stack (a few MB);
newand containers likevectoruse the large heap. - Explain Euclid's algorithm. gcd(a, b) = gcd(b, a % b) until b = 0; O(log) steps.
- Relation between GCD and LCM?
a × b = gcd × lcm; computelcm = a / gcd × bto avoid overflow. - What are
std::gcdandstd::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 / iso 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 * boverflows anint. C++17 hasstd::gcdandstd::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).