C Program to Check Whether a Number is Prime or Not

Check Prime (Brute Force)

#include <stdio.h>
int main() {
    int n, i, count = 0;
    printf("Enter a positive integer: ");
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        if (n % i == 0) {
            count++;
        }
    }
    if (n > 1 && count == 2) {
        printf("%d is a prime number.\n", n);
    } else {
        printf("%d is not a prime number.\n", n);
    }
    return 0;
}

Enter a positive integer: 7
7 is a prime number.

The brute force method iterates from 1 to n, counting how many numbers divide n. If exactly two numbers (1 and n) divide it, then n is prime.

Check Prime (Square Root Method)

#include <stdio.h>
#include <math.h>
int main() {
    int n, i, flag = 0;
    printf("Enter a positive integer: ");
    scanf("%d", &n);
    if (n <= 1) flag = 1;
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        printf("%d is a prime number.\n", n);
    else
        printf("%d is not a prime number.\n", n);
    return 0;
}

Enter a positive integer: 9
9 is not a prime number.

By observing that a composite number must have a factor less than or equal to its square root, this method only tests divisibility up to sqrt(n). If no divisor is found, the number is prime.

Check Prime (Skip Even Numbers)

#include <stdio.h>
int main() {
    int n, i, flag = 0;
    printf("Enter a positive integer: ");
    scanf("%d", &n);
    if (n <= 1) flag = 1;
    else if (n > 2 && n % 2 == 0) flag = 1;
    for (i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        printf("%d is a prime number.\n", n);
    else
        printf("%d is not a prime number.\n", n);
    return 0;
}

Enter a positive integer: 17
17 is a prime number.

Skipping even numbers after checking for n > 2 reduces the number of iterations. The loop tests only odd divisors up to the square root of n, making it more efficient than the brute force method.

C Program to Check if a Number Is Prime - Brute Force, Square Root & Odd Only

Check Prime (Brute Force)

Check Prime (Square Root Method)

Check Prime (Skip Even Numbers)

Comments

C Control Flow❯

C Program to Check if a Number Is Prime - Brute Force, Square Root & Odd Only

Check Prime (Brute Force)

Check Prime (Square Root Method)

Check Prime (Skip Even Numbers)

Comments

C Control Flow❯

Player Settings