These are the notes for C Coding Questions, episode 4, placement practice for people who finished the SyntaxPilot C course. Three number questions where the first answer is usually correct but too slow: is n prime, all primes up to n (the Sieve of Eratosthenes) and Armstrong numbers. Along the way: a real Time Limit Exceeded, a real Segmentation fault, and the edge cases 0, 1 and negatives.
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 gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int, 64-bit long long, 8 MB stack), the SyntaxPilot compiler's C command with warnings on, and every output below is real. Like an online judge, the compiler stops a program after 8 seconds and reports Time Limit Exceeded.
What a prime is: laddoos in a box
A sweet shop packs laddoos in a box in equal rows.
| Laddoos | Rectangles | In C | Prime? |
|---|---|---|---|
| 12 | 1 × 12, 2 × 6, 3 × 4 | 12 % 3 == 0: 3 is a divisor of 12 |
no |
| 13 | only 1 × 13 | no i from 2 to 12 gives 13 % i == 0 |
yes |
| 1 or 0 | nothing to arrange | no (primes start at 2) |
A prime number is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, … A number greater than 1 that is not prime is composite (it has another divisor). 0 and 1 are neither, and negative numbers are not prime.
A divisor (or factor) of n is a number that divides n exactly: n % d == 0.
Q1: Is n prime?
Problem. Read t, the number of test cases, then t integers. For each n, print n is prime or n is not prime. n can be any int. The program must finish within 8 seconds.
| Input | Output |
|---|---|
7 |
7 is prime |
12 |
12 is not prime |
1 |
1 is not prime |
0, -7 |
not prime |
2147483647 (INT_MAX) |
2147483647 is prime |
Think out loud
Try every i from 2 to n - 1; if any divides n, it is not prime, and we can stop at once with break. while (t--) runs the body exactly t times: it tests t, then decreases it. Edge cases: 1, 0, negatives, 2 (the smallest prime) and a huge prime, where no divisor is ever found.
The obvious attempt
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int prime = 1;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
prime = 0;
break;
}
}
if (prime) printf("%d is prime\n", n);
else printf("%d is not prime\n", n);
}
return 0;
}
Input 6 7 12 1 0 -7 97 (one per line):
7 is prime
12 is not prime
1 is prime
0 is prime
-7 is prime
97 is prime
- 1, 0 and -7 are reported as prime. For
n < 3the loopi = 2; i < nnever runs, soprimestays 1. - Three primes near
INT_MAX:
Input 3 2147483647 2147483629 2147483587:
Time Limit Exceeded (stopped after 8 seconds, no output)
For a prime near INT_MAX the loop does more than two billion divisions, so three of them (about 6.4 billion) cannot finish in 8 seconds. One 2147483647 alone took about 4.6 seconds on this machine.
Why: divisors come in pairs
36 laddoos: 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6. Every divisor a has a partner b = n / a, and the smaller of the two is at most √n (the square root: the number that multiplied by itself gives n; √36 = 6). So if n has any divisor other than 1 and n, it has one ≤ √n. Checking 7 … 35 only finds partners of divisors we already tried.
Writing "up to √n" safely
| Loop condition | Problem |
|---|---|
i < n |
O(n): too slow |
i <= sqrt(n) |
uses double from <math.h>; works, but mixes floating point into an integer question and recomputes sqrt each turn unless you store it |
i * i <= n |
near INT_MAX, i reaches 46,341 and 46,341² = 2,147,488,281 > INT_MAX: signed overflow, undefined behaviour |
i <= n / i |
the same test with a division: cannot overflow |
Undefined behaviour (UB) means the C standard promises nothing about what the program does. Never rely on it.
The fix
Two changes: int prime = (n >= 2); (false for 1, 0 and every negative) and i <= n / i.
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int prime = (n >= 2);
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
prime = 0;
break;
}
}
if (prime) printf("%d is prime\n", n);
else printf("%d is not prime\n", n);
}
return 0;
}
Input 6 7 12 1 0 -7 97:
7 is prime
12 is not prime
1 is not prime
0 is not prime
-7 is not prime
97 is prime
Input 3 2147483647 2147483629 2147483587:
2147483647 is prime
2147483629 is prime
2147483587 is prime
Input 3 2 4 2147483646:
2 is prime
4 is not prime
2147483646 is not prime
How many checks for INT_MAX now?
#include <stdio.h>
int main() {
int n = 2147483647, checks = 0;
for (int i = 2; i <= n / i; i++) checks++;
printf("%d checks\n", checks);
return 0;
}
Output:
46339 checks
Complexity: O(√n) time per number (46,339 loop turns instead of 2,147,483,645), O(1) space. Big O notation describes how the work grows as the input grows, ignoring constant factors.
Q2: All primes up to n
Problem. Read n (up to 30,000,000). Print every prime ≤ n when n ≤ 100, and always print how many primes there are and the largest one.
| Input | Output |
|---|---|
30 |
2 3 5 7 11 13 17 19 23 29 then count = 10, largest = 29 |
30000000 |
count = 1857859, largest = 29999999 |
1 |
count = 0, largest = 0 |
The obvious attempt: is_prime for every number
#include <stdio.h>
int is_prime(int n) {
if (n < 2) return 0;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int n, count = 0, last = 0;
scanf("%d", &n);
for (int x = 2; x <= n; x++) {
if (is_prime(x)) {
count++;
last = x;
if (n <= 100) printf("%d ", x);
}
}
if (n <= 100 && count > 0) printf("\n");
printf("count = %d, largest = %d\n", count, last);
return 0;
}
Input 30:
2 3 5 7 11 13 17 19 23 29
count = 10, largest = 29
Input 30000000:
Time Limit Exceeded (stopped after 8 seconds, no output)
Thirty million numbers, each needing up to √x ≈ 5,477 divisions: far too much. (It takes about 18 seconds on this machine.)
The Sieve of Eratosthenes
Turn the question around: instead of testing numbers, cross out the numbers that can't be prime. A sieve is a strainer; this one is named after the Greek mathematician Eratosthenes.
- Write 2 … n on a board.
- Take the smallest uncrossed number
i: it is prime. Cross out its multiples, starting ati × i(smaller multiples like2i,3iwere already crossed by smaller primes). - Repeat while
i × i ≤ n(writteni <= n / i). - Every number left uncrossed is prime.
For n = 30: 2 crosses 4, 6, 8, …, 30; 3 crosses 9, 15, 21, 27 (12, 18, 24, 30 were already crossed); 5 crosses 25; 6 × 6 > 30, stop. Left: 2 3 5 7 11 13 17 19 23 29.
In C the board is an array char composite[n + 1]: 0 = not crossed, 1 = crossed. Inside the loop, j = i * i can't overflow because i <= n / i guarantees i * i <= n.
First sieve: the array inside main
#include <stdio.h>
int main() {
int n, count = 0, last = 0;
scanf("%d", &n);
char composite[30000001] = {0};
for (int i = 2; i <= n / i; i++) {
if (!composite[i]) {
for (int j = i * i; j <= n; j += i) composite[j] = 1;
}
}
for (int x = 2; x <= n; x++) {
if (!composite[x]) {
count++;
last = x;
if (n <= 100) printf("%d ", x);
}
}
if (n <= 100 && count > 0) printf("\n");
printf("count = %d, largest = %d\n", count, last);
return 0;
}
Input 30:
Segmentation fault
It crashes even for 30, before printing anything. Local variables live on the stack, a memory area that is small (8 MB here, often 1 MB on Windows). A 30 MB array does not fit; the program touches memory it doesn't own and the operating system stops it: a segmentation fault. gcc gives no warning.
The fix: a global array
A variable declared outside every function is global. Globals have static storage: they exist for the whole run, live outside the stack, and start filled with zeros. (static char composite[...] inside main works too, or calloc.)
#include <stdio.h>
#define MAX 30000000
char composite[MAX + 1];
int main() {
int n, count = 0, last = 0;
scanf("%d", &n);
if (n > MAX) n = MAX;
for (int i = 2; i <= n / i; i++) {
if (!composite[i]) {
for (int j = i * i; j <= n; j += i) composite[j] = 1;
}
}
for (int x = 2; x <= n; x++) {
if (!composite[x]) {
count++;
last = x;
if (n <= 100) printf("%d ", x);
}
}
if (n <= 100 && count > 0) printf("\n");
printf("count = %d, largest = %d\n", count, last);
return 0;
}
Input 30:
2 3 5 7 11 13 17 19 23 29
count = 10, largest = 29
Input 30000000:
count = 1857859, largest = 29999999
Input 1:
count = 0, largest = 0
Input 2:
2
count = 1, largest = 2
Input 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
count = 25, largest = 97
The sieve answers 30,000,000 in about 0.2 seconds on this machine.
Complexity: the crossings are n/2 + n/3 + n/5 + n/7 + … ≈ O(n log log n) time. log log n is below 4 for any n you will meet, so this is almost linear. Space: O(n), one char per number (30 MB here). It trades memory for time.
Q3: Armstrong number
Problem. A number with d digits is an Armstrong number (also called a narcissistic number) when the sum of its digits, each raised to the power d, equals the number. Read an int n and say whether it is one.
| n | digits | sum | Armstrong? |
|---|---|---|---|
| 153 | 3 | 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 | yes |
| 1634 | 4 | 1⁴ + 6⁴ + 3⁴ + 4⁴ = 1 + 1296 + 81 + 256 = 1634 | yes |
| 9474 | 4 | 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 | yes |
| 7 | 1 | 7¹ = 7 | yes (every single digit) |
| 10 | 2 | 1² + 0² = 1 | no |
| 0 | 1 | 0¹ = 0 | yes |
| -153 | no (negatives are not Armstrong) |
The obvious attempt: cubes
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int x = n, sum = 0;
while (x > 0) {
int d = x % 10;
sum = sum + d * d * d;
x = x / 10;
}
if (sum == n) printf("%d is an Armstrong number\n", n);
else printf("%d is not an Armstrong number\n", n);
return 0;
}
Input 153:
153 is an Armstrong number
Input 1634:
1634 is not an Armstrong number
Input 7:
7 is not an Armstrong number
The power is hard-coded to 3, which is only right for three-digit numbers. For 7 it compared 343 with 7.
The fix: count the digits first
- Count the digits with a do-while loop (its body runs once before the condition is checked, so 0 has 1 digit).
- Raise each digit to that power with an integer loop.
- Use
long longfor the powers and the sum: a 10-digitintcan produce 9¹⁰ = 3,486,784,401 >INT_MAX. - Avoid
pow()from<math.h>here: it works withdouble(floating point), and converting a slightly-off result like 124.99999 tointgives 124. Integer questions deserve integer arithmetic.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n < 0) {
printf("%d is not an Armstrong number\n", n);
return 0;
}
int digits = 0, x = n;
do {
digits++;
x = x / 10;
} while (x > 0);
long long sum = 0;
x = n;
while (x > 0) {
int d = x % 10;
long long p = 1;
for (int k = 0; k < digits; k++) p = p * d;
sum = sum + p;
x = x / 10;
}
if (sum == n) printf("%d is an Armstrong number\n", n);
else printf("%d is not an Armstrong number\n", n);
return 0;
}
Input 1634:
1634 is an Armstrong number
Input 7:
7 is an Armstrong number
Input 9474:
9474 is an Armstrong number
Input 10:
10 is not an Armstrong number
Input -153:
-153 is not an Armstrong number
Input 0:
0 is an Armstrong number
Input 2147483647:
2147483647 is not an Armstrong number
Complexity: d digits × d multiplications = O(d²) = O((log n)²) time, at most 100 steps for an int; O(1) space.
Complexity summary
| Question | Obvious attempt | Fixed | Extra space |
|---|---|---|---|
| Is n prime? | O(n) per number | O(√n) per number | O(1) |
| All primes up to n | about O(n√n) | O(n log log n) (sieve) | O(n) |
| Armstrong number | wrong for d ≠ 3 | O((log n)²) | O(1) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int prime = 1; and i < n for n = 1 |
no error: 1 is prime (also 0, -7) |
the loop never runs for n < 3 | int prime = (n >= 2); |
for (i = 2; i < n; i++) with n ≈ 2 × 10⁹ |
Time Limit Exceeded |
O(n) checks | i <= n / i: O(√n) |
for (i = 2; i * i <= n; i++) |
no warning; i * i overflows near INT_MAX |
signed overflow is undefined behaviour | i <= n / i |
is_prime(x) for every x up to 3 × 10⁷ |
Time Limit Exceeded |
n × √n work | Sieve of Eratosthenes |
char composite[30000001]; inside main |
Segmentation fault |
30 MB on an 8 MB stack | a global (or static) array |
Sieve starting at 2 * i |
correct but slower | multiples below i * i are already crossed |
start at i * i |
sum += d * d * d; |
no error: 1634 is not an Armstrong number |
the power must be the digit count | count digits first |
sum += pow(d, digits); into an int |
can be off by one on some compilers | pow returns a rounded double |
an integer power loop |
Your turn: prime factors (solution)
Problem. Read n ≥ 2 and print its prime factors, smallest first, with repeats: 360 → 2 2 2 3 3 5 (2 × 2 × 2 × 3 × 3 × 5 = 360).
Idea. For i from 2 while i <= n / i: while i divides n, print i and divide n by it. Because smaller factors are divided out first, every i that divides is prime. The trap: whatever is left above 1 at the end is itself a prime factor (for 97, or the 331 in 2147483646).
Show the solution
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n < 2) {
printf("enter a number of 2 or more\n");
return 0;
}
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
printf("%d ", i);
n = n / i;
}
}
if (n > 1) printf("%d", n);
printf("\n");
return 0;
}
Input 360:
2 2 2 3 3 5
Input 97:
97
Input 2147483646:
2 3 3 7 11 31 151 331
Input 1024:
2 2 2 2 2 2 2 2 2 2
Input 2147483647:
2147483647
Input 1:
enter a number of 2 or more
Time O(√n) in the worst case (when n is prime), space O(1).
Practice questions (with solutions)
1. Count the primes between a and b (inclusive), b ≤ 30,000,000.
Solution
#include <stdio.h>
#define MAX 30000000
char composite[MAX + 1];
int main() {
int a, b;
scanf("%d %d", &a, &b);
if (a < 0) a = 0;
if (b > MAX) b = MAX;
for (int i = 2; i <= b / i; i++) {
if (!composite[i]) {
for (int j = i * i; j <= b; j += i) composite[j] = 1;
}
}
int count = 0;
for (int x = (a < 2 ? 2 : a); x <= b; x++) {
if (!composite[x]) count++;
}
printf("%d\n", count);
return 0;
}
Input 1 30:
10
Input 10 20:
4
Input 0 30000000:
1857859
Input 24 28:
0
Time O(b log log b), space O(b).
2. Print all Armstrong numbers from 1 to 100,000.
Solution
#include <stdio.h>
int is_armstrong(int n) {
int digits = 0, x = n;
do {
digits++;
x = x / 10;
} while (x > 0);
long long sum = 0;
for (x = n; x > 0; x = x / 10) {
long long p = 1;
for (int k = 0; k < digits; k++) p = p * (x % 10);
sum = sum + p;
}
return sum == n;
}
int main() {
for (int n = 1; n <= 100000; n++) {
if (is_armstrong(n)) printf("%d ", n);
}
printf("\n");
return 0;
}
Output:
1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084
3. Twin primes up to n (pairs p, p + 2 that are both prime, n ≤ 1,000,000).
Solution
#include <stdio.h>
#define MAX 1000000
char composite[MAX + 1];
int main() {
int n;
scanf("%d", &n);
if (n > MAX) n = MAX;
composite[0] = composite[1] = 1;
for (int i = 2; i <= n / i; i++) {
if (!composite[i]) {
for (int j = i * i; j <= n; j += i) composite[j] = 1;
}
}
int pairs = 0;
for (int p = 2; p + 2 <= n; p++) {
if (!composite[p] && !composite[p + 2]) {
pairs++;
if (n <= 100) printf("(%d, %d) ", p, p + 2);
}
}
if (n <= 100 && pairs > 0) printf("\n");
printf("%d pairs\n", pairs);
return 0;
}
Input 30:
(3, 5) (5, 7) (11, 13) (17, 19)
4 pairs
Input 100:
(3, 5) (5, 7) (11, 13) (17, 19) (29, 31) (41, 43) (59, 61) (71, 73)
8 pairs
Input 1000000:
8169 pairs
Input 4:
0 pairs
Quick quiz
int n = 97, count = 0;
for (int i = 2; i <= n / i; i++)
count++;
printf("%d\n", count);
(A) 8 (B) 9 (C) 48 (D) 95
Answer
(A) 8. i takes 2, 3, …, 9. At i = 9: 97 / 9 = 10, and 9 ≤ 10. At i = 10: 97 / 10 = 9, and 10 > 9, stop. √97 ≈ 9.85.
Interview questions
- Why check divisors only up to √n? Divisors pair up as a × b = n, and the smaller of each pair is ≤ √n. If none is found up to √n, n is prime.
- Is 1 a prime number? No. A prime has exactly two divisors, 1 and itself; 1 has only one.
- Why write
i <= n / iinstead ofi * i <= n?i * ican overflow anintnearINT_MAX(undefined behaviour); the division cannot. - What is the time complexity of the Sieve of Eratosthenes? O(n log log n) time, O(n) space.
- Why does the inner sieve loop start at
i * i? Every smaller multiplek × iwith k < i has a smaller prime factor and was already crossed. - Why does a big local array crash? Local variables live on the stack, which is only a few MB; use a global,
staticormalloc/callocarray. - When would you use a sieve instead of trial division? When you need many prime checks or all primes up to a limit; for a single number, trial division up to √n is enough.
- Is 0 an Armstrong number? Yes: it has one digit, and 0¹ = 0.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Divisor (factor) | A number that divides n exactly | 3 is a divisor of 12: 12 % 3 == 0 |
| Prime number | A whole number > 1 whose only divisors are 1 and itself | 2, 3, 5, 7, 13 |
| Composite number | A whole number > 1 that is not prime | 12 = 3 × 4 |
| Prime factor | A prime that divides n | 360 = 2³ × 3² × 5 |
| Square root (√n) | The number that multiplied by itself gives n | √36 = 6 |
| Test case | One input the program must answer; a judge sends many | t numbers after t |
while (t--) |
Runs the body exactly t times (tests t, then decreases it) | 6 test cases → 6 turns |
break |
Leaves the loop at once | stop at the first divisor |
| Time Limit Exceeded (TLE) | The judge stopped the program for running too long | 8 seconds here |
| Big O notation | How the work grows with the input, ignoring constants | O(n), O(√n) |
| Time complexity | How the running time grows with the input | O(√n) prime check |
| Space complexity | How the extra memory grows with the input | O(n) for the sieve |
| Signed integer overflow | A signed result too big for its type: undefined behaviour | 46341 * 46341 in an int |
| Undefined behaviour (UB) | Code whose result the C standard doesn't define | signed overflow |
| Sieve of Eratosthenes | Find all primes ≤ n by crossing out multiples of each prime | primes up to 30,000,000 in 0.2 s |
| Stack | Memory for local variables and function calls; small (about 8 MB here) | char a[30000001] in main crashes |
| Segmentation fault | The OS stops a program that touched memory it doesn't own | a stack overflow |
| Global variable | Declared outside every function; visible everywhere | char composite[MAX + 1]; |
| Static storage | Memory that lasts for the whole run and starts at zero | globals, static locals |
#define |
A named constant replaced before compiling | #define MAX 30000000 |
| Armstrong number | Equals the sum of its digits, each to the power of the digit count | 153, 1634, 9474 |
do-while loop |
Runs its body once before checking the condition | counting the digits of 0 |
pow() |
<math.h> power function; works in double |
pow(2, 10) = 1024.0 |
long long |
An integer type of at least 64 bits | sums of 10th powers |
| Edge case | An input at the boundary | 0, 1, negatives, INT_MAX |
Summary
- A prime is > 1 with only 1 and itself as divisors; 0, 1 and negatives are not prime.
- Divisors pair up, so test only up to √n, written
i <= n / i(no overflow): O(√n). - For all primes up to n, use the Sieve of Eratosthenes: cross out multiples from
i * i; O(n log log n) time, O(n) space. - Big arrays go global (static storage): the stack is only a few MB, and overflowing it is a segmentation fault.
- Armstrong numbers: count the digits first (do-while), then integer powers in
long long.
Next episode: Number questions III: GCD and LCM (Euclid's algorithm), factorial and integer overflow (int vs long long vs unsigned), the n-th Fibonacci number (loop vs naive recursion).