Skip to lab content

UNIT 02 · Expression Evaluation

Test whether a number is prime

EXERCISE 02BC173 sample runs

THE SYLLABUS QUESTION

What you need to solve

Write a program that finds if a given number is a prime number.
Input format & conventions

One integer between -1,000,000,000 and 1,000,000,000.

UNDERSTAND THE IDEA

Explanation

A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Numbers below 2 are not prime.

If a composite number has a divisor, at least one divisor is no greater than its square root. The condition divisor <= number / divisor avoids overflow from divisor * divisor.

PLAN BEFORE CODING

Algorithm

  1. Read the integer and validate its range.
  2. Treat numbers less than 2 as not prime.
  3. Test divisors from 2 while divisor <= number / divisor.
  4. Stop if a divisor divides the number exactly.
  5. Print the primality result.

SEE THE CONTROL FLOW

Flowchart

Follow the arrows from Start. Diamonds ask a question; labeled arrows show the answer. A returning arrow repeats a loop. Function internals are grouped where needed; later input checks follow the rules in the program.

Flowchart for Test whether a number is prime: input, decisions, processing, output and loop paths

On a phone, scroll sideways to read the diagram at full size. Open full-size flowchart ↗

C17

Complete C program

Download .c
#include <stdio.h>

int main(void) {
    int number, prime;
    if (scanf("%d", &number) != 1 || number < -1000000000 || number > 1000000000) {
        puts("Invalid input.");
        return 1;
    }
    prime = number >= 2;
    for (int divisor = 2; prime && divisor <= number / divisor; ++divisor) {
        if (number % divisor == 0) prime = 0;
    }
    printf("%d is %sprime.\n", number, prime ? "" : "not ");
    return 0;
}
Open in compiler ↗

Code loads into the existing compiler. Enter the sample input there; sign-in and execution rules stay the same.

Compile and run locally
gcc -std=c17 prime-number.c -o lab
./lab

On Windows, run .\lab.exe after compiling with GCC. The interest program requires the math library where applicable.

FOLLOW THE VALUES

Dry run

Step / stateOperationResult
Input 29Try divisor 2Remainder 1
Try divisors 3, 4, 5No zero remainderStill prime candidate
Next divisor 66 > 29 / 6Stop: 29 is prime

CHECK THE BEHAVIOR

Sample input & output

Each output below was produced by compiling and running this exact program. Input values are entered in the stated order; the examples do not print input prompts.

Sample 1

INPUT 
29
OUTPUT
29 is prime.

Sample 2

INPUT 
1
OUTPUT
1 is not prime.

Sample 3

INPUT 
49
OUTPUT
49 is not prime.

Common mistakes

  • One and zero are not prime.
  • Use a safe loop bound instead of squaring a potentially large divisor.

WHY THIS GROWTH RATE?

Time and space complexity

Time O(√n) for n >= 2; auxiliary space O(1).

Let n be the value being tested. If n has a factor larger than √n, its partner factor must be smaller than √n. Therefore the loop only needs to test divisors up to √n, using divisor <= n / divisor to avoid multiplying two divisors.

For a prime input, no early exit occurs and roughly √n divisors are tested. Each remainder test has constant cost for fixed-width integers, giving worst-case O(√n) time. Inputs below 2, or an early factor such as 2, finish in O(1). Only a few counters and flags are stored: O(1) auxiliary space.

Big-O describes how work grows as the stated input quantity grows; fixed factors and lower-order terms are omitted. The analysis treats fixed-width arithmetic as constant cost and the published limits as practical safety bounds.