SyntaxPilot
Courses/C Coding Questions/Lesson 4
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 4 of 30

Number questions II

prime check (why up to √n)all primes up to n (Sieve of Eratosthenes)Armstrong number

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. 1, 0 and -7 are reported as prime. For n < 3 the loop i = 2; i < n never runs, so prime stays 1.
  2. 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.

  1. Write 2 … n on a board.
  2. Take the smallest uncrossed number i: it is prime. Cross out its multiples, starting at i × i (smaller multiples like 2i, 3i were already crossed by smaller primes).
  3. Repeat while i × i ≤ n (written i <= n / i).
  4. 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

  1. Count the digits with a do-while loop (its body runs once before the condition is checked, so 0 has 1 digit).
  2. Raise each digit to that power with an integer loop.
  3. Use long long for the powers and the sum: a 10-digit int can produce 9¹⁰ = 3,486,784,401 > INT_MAX.
  4. Avoid pow() from <math.h> here: it works with double (floating point), and converting a slightly-off result like 124.99999 to int gives 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

  1. 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.
  2. Is 1 a prime number? No. A prime has exactly two divisors, 1 and itself; 1 has only one.
  3. Why write i <= n / i instead of i * i <= n? i * i can overflow an int near INT_MAX (undefined behaviour); the division cannot.
  4. What is the time complexity of the Sieve of Eratosthenes? O(n log log n) time, O(n) space.
  5. Why does the inner sieve loop start at i * i? Every smaller multiple k × i with k < i has a smaller prime factor and was already crossed.
  6. Why does a big local array crash? Local variables live on the stack, which is only a few MB; use a global, static or malloc/calloc array.
  7. 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.
  8. 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).