Algorithm of checking if the number is prime

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1

Implementation of the above:

#include <iostream>

bool isPrime(int n) {
    // Corner cases
    if(n <= 1) return false;
    if(n <= 3) return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if(n % 2 == 0 || n % 3 == 0) return false;

    for(int i = 5; i * i <= n; i = i + 6)
        if(n % i == 0 || n % (i + 2) == 0) return false;

    return true;
}

// Driver Program to test above function
int main() {
    std::cout << std::boolalpha
        << isPrime(11) << '\n'
        << isPrime(15) << '\n';
}

A number that is not prime will be divisible by at least one prime number. Hence a way to speed up the algorithm (at the cost of memory) would be to store a list of the prime numbers you have already encountered, and only check whether any of these divide the number you are currently checking in each iteration.

To make this more efficient, don't calculate the sqrt of the number
You don't need to check the even numbers if they are divisors.
Also, it's handy to have an early exit in case the number is negative.
Here is my code in C:

#define  boolean  int
#define   TRUE     1
#define   FALSE    0

boolean
isPrime(int number)
{
    if(number == 2)
        return TRUE;

    if(number < 2 || number % 2 == 0)
        return FALSE;

    /*
     * we only need to check until the sqrt
     * and we can omit the even numbers as well
     */
    for(int i = 3; i*i <= number; i += 2)
        if(number % i == 0)
            return FALSE;

    return TRUE;
}

1. 2 is the only even prime. So if you start you loop form 3 and increase i by 2, then you can cut off the loop by half.

2. And you can break as soon as you find the first divisor.

3. Assign the sqrt(num) into a variable so that it does not calculated on every iteration.

    if (num == 2)
    {
        return 1;
    }
    if (num % 2 == 0)
    {
        return 0;
    }
    int square_root = sqrt(num);
    for (int i = 3; i <= square_root; i += 2)
    {
        if (num % i == 0)
        {
            isPrime = 0;
            break;
        }
    }