What is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples of primes include: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

The number 2 is the only even prime number.

Optimized O(√n) Prime Check Algorithm

Rather than checking all integers up to $n-1$, we only need to test divisibility up to $⌊√n⌋$. If n has a factor larger than $√n$, it must also have a corresponding factor smaller than $√n$.

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdbool.h>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    if (n <= 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }

    /* Check factors of the form 6k ± 1 up to sqrt(n) */
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int testNumber = 29;

    if (isPrime(testNumber)) {
        printf("%d is a Prime number.\n", testNumber);
    } else {
        printf("%d is NOT a Prime number.\n", testNumber);
    }

    printf("\nAll Prime numbers between 10 and 50:\n");
    for (int i = 10; i <= 50; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

Expected Output

text (ISO Standard)
Copy
29 is a Prime number.

All Prime numbers between 10 and 50:
11 13 17 19 23 29 31 37 41 43 47 

Algorithmic Complexity

Related Guides & Examples

• Check numerical symmetry with our Palindrome Program in C.
• Generate mathematical terms with the Fibonacci Series in C.
• Master loops and operators in C Programming Basics.