how to check if a number is prime?

A prime number can only have two dividers, itself and the unit. It should be noted that any number is divisible by itself and by number one, the particularity of the prime number lies in the fact that it doesn't have any other dividers. Before analyzing how this can be tested using a programming language, you can try to check if a number is prime, by entering that number directly in the following box:

How to test if a number is prime using a programming language?

The easiest way to test whether a number is prime or not prime, is to divide the number successively by all the numbers between two and the number itself minus one. This is because we know that any number is divisible by one and by itself. If the division gives a remainder equal to zero, then a divider of the number has been found. As soon as we find a divider, we can interrupt the repetition cycle and affirm that it is not a prime. If all divisions are made, without being able to find a single divider, then the number is prime:

function checkPrime($number){ 
	for ($i = 2; $i < $number-1; $i++){ 
		if ($number % $i == 0) 
			return false; 
	} 
	return true; 
}
	

The code presented above can, however, be improved. Note that if we are testing whether the number 97 is prime, the repetition structure will perform 95 divisions (divides all numbers between 2 and 96), but this is unnecessary. No number has a divider greater than half its value. Therefore, the code can be improved, so that the cycle stops as soon as it reaches half the number to be analyzed:

function checkPrime($number){ 
	for ($i = 2; $i < $number/2; $i++){ 
		if ($number % $i == 0) 
			return false; 
	} 
	return true; 
}
	

At this point, if we are testing whether the number 97 is prime, the repetition structure will only make 47 divisions (divides all numbers between 2 and 48), but this can still be improved. Any divider of the number greater than its square root is a factor of a smaller divider already tested. In this way, the code can be optimized, so that the repetition cycle stops as soon as it reaches the square root of the number we intend to test:

function checkPrime($number){ 
	for ($i = 2; $i < sqrt($number); $i++){ 
		if ($number % $i == 0) 
			return false; 
	} 
	return true; 
}
	

In this last example, to test whether the number 97 is prime, only 8 divisions will be made (divides by all numbers between 2 and 9). This low number of divisions is already a significant improvement over the first version of the code. New features could still be introduced in the algorithm, in order to ensure that its execution is even faster. But given that this implies more advanced knowledge of mathematics, let us stop here ...

Check out our List of Questions to get to know a little more about the most diverse topics related to mathematics. If you have any pertinent (math) question whose answer can not easily be found, send us an email on the Contact page with the question. We will be happy to respond. In the event that you detect any errors in our answers, do not hesitate to contact us!