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.
Latest comments (0)