Check if a Number is Prime in C

Introduction

In this lab, we will learn how to check if a number is prime in C programming. The lab consists of three steps: reading an integer input from the user, testing divisibility from 2 to the square root of the number, and printing whether the number is prime or not. By the end of this lab, you will have a working program that can determine the primality of a given integer.

The lab starts by teaching how to read an integer input from the user using the scanf() function. Then, it introduces the prime number checking algorithm, which involves testing divisibility from 2 to the square root of the input number. If no divisors are found, the number is considered prime. Finally, the program prints the result, indicating whether the number is prime or not.

Skills Graph

Read an Integer

In this step, we will learn how to read an integer input from the user in C programming. This is the first step in creating a prime number checker.

First, let's create a new C file for our prime number checking program:

cd ~/project
nano prime_checker.c

Now, let's write the code to read an integer:

#include <stdio.h>

int main() {
    int number;

    printf("Enter a positive integer to check if it's prime: ");
    scanf("%d", &number);

    printf("You entered: %d\n", number);

    return 0;
}

Example output:

Enter a positive integer to check if it's prime: 17
You entered: 17

Let's break down the code:

• #include <stdio.h> includes the standard input/output library
• int main() is the main function where program execution begins
• int number; declares an integer variable to store user input
• printf() displays a prompt to the user
• scanf() reads an integer input from the user and stores it in number
• printf() confirms the number entered by the user

Compile and run the program:

gcc prime_checker.c -o prime_checker
./prime_checker

Test Divisibility from 2 to √n

In this step, we will implement the prime number checking algorithm by testing divisibility from 2 to the square root of the input number.

Let's modify our previous C program to add the prime number checking logic:

nano ~/project/prime_checker.c

Update the code with the divisibility test:

#include <stdio.h>
#include <math.h>

int is_prime(int number) {
    // Numbers less than 2 are not prime
    if (number < 2) {
        return 0;
    }

    // Check divisibility from 2 to square root of number
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return 0; // Not prime if divisible
        }
    }

    return 1; // Prime if no divisors found
}

int main() {
    int number;

    printf("Enter a positive integer to check if it's prime: ");
    scanf("%d", &number);

    if (is_prime(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Compile the program with math library:

gcc ~/project/prime_checker.c -o ~/project/prime_checker -lm

Example outputs:

Enter a positive integer to check if it's prime: 17
17 is a prime number.

Enter a positive integer to check if it's prime: 20
20 is not a prime number.

Key points about the implementation:

• sqrt() function from <math.h> calculates square root
• We only check divisibility up to √n to optimize the algorithm
• If no divisors are found, the number is prime
• The modulo operator % checks divisibility
• We return 0 for non-prime, 1 for prime numbers

Print If Prime or Not

In this final step, we will enhance our prime number checking program by adding more detailed output and allowing multiple number checks.

Let's modify the program to provide more comprehensive output:

nano ~/project/prime_checker.c

Update the code with an improved interface:

#include <stdio.h>
#include <math.h>

int is_prime(int number) {
    // Numbers less than 2 are not prime
    if (number < 2) {
        return 0;
    }

    // Check divisibility from 2 to square root of number
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return 0; // Not prime if divisible
        }
    }

    return 1; // Prime if no divisors found
}

void print_prime_details(int number) {
    if (is_prime(number)) {
        printf("%d is a PRIME number!\n", number);
        printf("Explanation:\n");
        printf("- It is only divisible by 1 and itself\n");
        printf("- No other divisors were found between 2 and √%d\n", number);
    } else {
        printf("%d is NOT a prime number.\n", number);

        // Find and print the smallest divisor
        for (int i = 2; i <= sqrt(number); i++) {
            if (number % i == 0) {
                printf("Explanation:\n");
                printf("- Divisible by %d\n", i);
                printf("- %d × %d = %d\n", i, number/i, number);
                break;
            }
        }
    }
}

int main() {
    int number, continue_check;

    do {
        printf("Enter a positive integer to check if it's prime: ");
        scanf("%d", &number);

        print_prime_details(number);

        printf("\nDo you want to check another number? (1=Yes, 0=No): ");
        scanf("%d", &continue_check);
    } while (continue_check == 1);

    printf("Thank you for using the Prime Number Checker!\n");

    return 0;
}

Compile the program:

gcc ~/project/prime_checker.c -o ~/project/prime_checker -lm

Example outputs:

Enter a positive integer to check if it's prime: 17
17 is a PRIME number!
Explanation:
- It is only divisible by 1 and itself
- No other divisors were found between 2 and √17

Do you want to check another number? (1=Yes, 0=No): 1

Enter a positive integer to check if it's prime: 20
20 is NOT a prime number.
Explanation:
- Divisible by 2
- 2 × 10 = 20

Do you want to check another number? (1=Yes, 0=No): 0
Thank you for using the Prime Number Checker!

Key improvements:

• Added detailed explanations for prime and non-prime numbers
• Implemented a loop to allow multiple number checks
• Provides more educational output about number properties

Summary

In this lab, we learned how to read an integer input from the user in C programming, which is the first step in creating a prime number checker. We then implemented the prime number checking algorithm by testing divisibility from 2 to the square root of the input number. The program checks if a given number is prime by iterating through the numbers from 2 to the square root of the number and checking if any of them divide the number evenly. If no divisors are found, the number is considered prime.