Algorithm of checking if the number is prime

Question

Hello everyone!

I came to this algorithm on how to check if number is prime and probably it's fine for me but I want to find out if it can be improved

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

    return isPrime;
}

Thanks in advance

It could certainly be improved by using `false` and `true` instead of `0` and `1`. — john, Jun 02 '20 at 10:40
It could also be improved by breaking out of the loop once you've found a number is not prime — john, Jun 02 '20 at 10:41
Do you mean 0 and 1 are considered as integers(in that case)? — NixoN, Jun 02 '20 at 10:42
You could also test `2` as a separate case and then write your loop as `for (int i = 3; i <= sqrt(num); i += 2)` You avoid checking the even numbers that way (apart from two of course). — john, Jun 02 '20 at 10:43
Your first two `if` checks can be made into one: `if (num <= 1)` and you can have `return false` in place of `isPrime = 0`. — Adrian Mole, Jun 02 '20 at 10:44
i do consider them as integers ;). They can be converted to `bool`, but why would you? You can also use `42` for `true`, but your code will be easier to read when you use `true` in places where you mean `true` — 463035818_is_not_an_ai, Jun 02 '20 at 10:44
What if the compiler doesn't hoist out `sqrt(num)` and calculates it for every iteration? Yikes! *Anyway...* shouldn't questions about working code be on Code Review instead? But I suspect one or both sites already has duplicates for this one. — underscore_d, Jun 02 '20 at 10:47
If your code works, post it in [Code Review](https://codereview.stackexchange.com/) to help improve it. — lnxkrnl, Jun 02 '20 at 10:53

score 7 · Accepted Answer · edited Jun 02 '20 at 10:58

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';
}

score 3 · Answer 2 · answered Jun 02 '20 at 10:57

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.

lnxkrnl · Answer 3 · 2020-06-02T10:54:16.193

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;
}

Rafik Farhad · Answer 4 · 2020-06-02T10:49:34.230

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.
And you can break as soon as you find the first divisor.
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;
        }
    }

edited Jun 02 '20 at 10:49

answered Jun 02 '20 at 10:43

Rafik Farhad

1,182
2
12
21

The idea is good, the implementation is poor. – john Jun 02 '20 at 10:46
2

What if the compiler doesn't hoist out `sqrt(num)` and calculates it for every iteration? Edit: I see that wasn't introduced by you, but still, yikes! ;-) – underscore_d Jun 02 '20 at 10:47
2

No guarantees the compiler will optimize out `sqrt(num)` on each iteration of the loop. Consider assigning that to a variable constant and let the for loop condition statement evaluate if `i < that value` – selbie Jun 02 '20 at 10:47
Oh sorry, I forgot to handle the even case, edited the answer. – Rafik Farhad Jun 02 '20 at 10:50

Algorithm of checking if the number is prime

4 Answers4