Prime numbers, a simple function in C++

A prime number is simply a number that is only divisible by one and itself. One of the most basic ways to find out if a number is prime, then, is to loop through every number (except for 1, as all positive integers are divisible by 1), and return true if the number is equally divisible by any other number except for itself.

This is a good example use of the modulus operator. The modulus operation returns the remainder of a division of two numbers. So, for example, 15 % 5 would equal 0, as 5 goes into 15 exactly 3 times with no remainder. 17 % 5 on the other hand would equal 2. As 5 goes into 17 3 times, with 2 being left over.

How it works:

Knowing this, and knowing what makes a prime number, we can check if a number is prime by checking every number between two and itself minus one, and if any of these numbers give us a modulus result of 0, then it is exactly divisible by another number and therefore not prime. If no modulus results of 0 are found by the time i is equal to x-1, then we know x to be prime. As each integer would always be divisible by itself, we have no need to check whether this is true or not. If we did want to check this, then our loop conditional statement would be i <= x;

This type of function is known as a predicate. A predicate is simply a function that returns true or false. In this instance, given an input of x, it will return true if the number is prime, and false if it is not.

If you wanted to implement this function and check every number beyond 1 to see if it was prime, you could do it like so;

This will iterate indefinitely until the maximum value that is able to be held in unsigned long int on your machine is reached. At that point, it will wrap around back to 0. You can use a larger data type, such as long long int, if your compiler supports it. But as you'll see, the main drawback of this function is that the larger the number gets, the more numbers it needs to check itself against to determine whether or not it is prime, so you may never reach that limit as it will take progressively longer each time to check the next number in the infinite while loop. The speed at which the program runs will depend on the processing power of the machine you are running it on.

If you needed to quickly check if a number is prime without needing to calculate it, then you could store the results in a text file, and check to see if that number exists in the file. If you store the results numerically, then you can stop searching once you reach the next prime number in the file beyond the one you're searching for. This is a very simple example of a lookup table, which saves computation time by storing the results of an operation rather than having to re-calculate them each time. This makes sense when you're performing a large number of checks of a particular calculation where the result is always going to be the same, and especially if you're going to be performing the same calculations many thousands of times over, and performance is a factor.

There are much more efficient techniques out there for finding prime numbers too, known as prime number sieves. One such algorithm is known as the Sieve of Eratosthenes, and I may follow up this post in future with a discussion on that.

Leave a Reply

Your email address will not be published. Required fields are marked *