Algorithms for primes number - introduction
Tags: programming, tutorial, cpp, computerscience
Published: 2022-05-25 22:00:52

Heellooo everybody🔥, Welcome back! 😎

Determining if a number is prime is a common problem in high school, the Olympics, and some contests or websites with algorithmic problems. Mathematicians have a high focus on prime numbers, they are really useful in cryptography area and in math in general. Being a prime number is a property studied in number theory, a really nice chapter for computer science which I will talk about in future posts.


There are plenty of solutions. All solutions return the correct answer, but **the difference is their time and space complexity**, a **core concept** in programming. We always search for **the most efficient approach**. I don’t want to cover complexity analysis in this post, but I will briefly present some complexities.

---

The first algorithm is:

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;
    }

    if (cnt >= 3) return 0;

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

```
This is the most basic solution. It follows exactly the mathematically definition of prime numbers - **A prime number has exactly two divisors**. We iterate from 1 until we reach our number, trying to find how many divisors exist. If there are more than 2, we return `0(false)` or `1(true)` if the number of divisors is smaller than 2. It is a good approach if you are new to algorithms.

We iterate the whole interval between 1 and the number passed as argument. This gave us a linear complexity, `O(n)`. Although this sounds good, we make some useless analyses for some numbers.

The first optimization we can do is **to stop right when we find that there are more than two divisors**, so our solution will look like this:

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;

        if (cnt >= 3) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}



```
Our complexity **still doesn't decrease**, but it is worth optimization, which makes our code better.

We can continue our improvements by not beginning to iterate from 1 because we know that 1 is the divisor for any number. Also, we can only iterate **till the half of the number** because we count for its divisors, and divisors of a number can be **found till the half of the number**. In this case, we can get rid of the divisor's counter because we start from 2 and stop at half, so it **is enough to find only one** divisor to say that the number **is not prime**. So our code will look like this:

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i <= Number / 2; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

```

Spoiler alert, our **time complexity didn’t change**. It is still a linear algorithm.
Why?
Because we make O(n/2) steps, and if we rewrite this like O(1/2 * n), 1/2 is constant, and we **don’t care about constants**, so we **remove** them, and we have O(n).

Another optimization is to iterate **till the square root of the number**. We know that divisors of a number are in pairs, so if we don’t find divisors between `[2, square root of the number]`, we will not find any divisors from the `[square root of the number, number]`. The code will look like this:

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i * i <= Number; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}
```

Now, the time complexity has changed. It became `O(sqrt(n))` because we iterate over `sqrt(n)` numbers. Even if we exclude 1, which will be O(sqrt(n) - 1), 1 is constant, so we don’t care. Thus we remove it.

Note that we used `i * i <= n` instead of using `sqrt(n)`. This is because `sqrt(n)` is a function which require time to complete and we prefer to avoid this time taken by calling `sqrt(n)`. Even worse will be to write the for loop like this `for (unsigned long long i = 1; i <= sqrt(Number); ++i)`. Writting code like this will repeatedly calling `sqrt()` function at every iteration wasting time and performance. Of course you can call `sqrt()` one time, save it into a variable and write something like this

```
unsigned long long square = sqrt(Number);
for (unsigned long long i = 1; i <= square; ++i)
```

But still we have another function call which require time. A cleaner and better way is to use `i * i <= Number` method.

Now I will show a final version.

1. Firstly we know that 0 and 1 are not primes.
2. Secondly, we know that every even number except 2 is not prime
3. Thirdly we see that it is enough if we can iterate till the square root of the number.

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    if (Number == 0 || Number == 1) return 0;

    else if (Number % 2 == 0 && Number != 2) return 0;

    else
    {
        for (unsigned long long i = 3; i * i <= Number; i += 2)
        {
            if (Number % i == 0) return 0;
        }
    }

    return 1;

}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}
```

We iterate over 2 numbers at once because we begin from 3, and if we iterate over 1 number at once, we will iterate over even numbers as well, but we **already checked if our number is even at the previous step**.

**Observation: This algorithm is commonly used for contests and Olympics.**

Another algorithm used for the primality test is the one for **finding prime factors**. When we have a power greater than 0, this means that we found a divisor so we can **stop**.

```
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long divisor = 2;

    while (Number > 1)
    {
        unsigned long long power = 0;

        if (Number % divisor == 0)
        {
            Number /= divisor;
            ++power;
        }

        if (power) return false;

        ++divisor;

        if (divisor * divisor > Number) return true;
    }
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}
```

Time complexity here is `O(sqrt(n))` in the wrost case. Because in a better case, the number is a power of divisor, for example, `Number = m^k`, where `m = 1, 2, 3, 4,...` and we perform `k` divisions which is `O(log(n))`.

---
Finally, we have done.

There can be many other improvements for the algorithms I showed and many others algorithms for the primality problem, but I think this is a solid introduction. Next time, I will show you another interesting algorithm called **Sieve of Eratosthenes**, used to find all prime numbers in a given interval. As a bonus, I will show you how this algorithm **can be combined** with the algorithm above to check the **primality** of a number. It is going to be a **complex** and fun algorithm.

---

- Emanuel Rusu

- You can visit my [GitHub](https://github.com/Emanuel181)

- Or you can find me on [Linkedin] (https://www.linkedin.com/in/rusu-emanuel/)

- Next topic: **Sieve of Eratosthenes**

- See you next time ! 👋