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.

- Firstly we know that 0 and 1 are not primes.
- Secondly, we know that every even number except 2 is not prime
- 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.

## Top comments (0)