Simple Script Prime Numbers

I was working with the Project Euler #3 and i need to check if a number is a prime, so i decided to post the script for checking if a number is a prime in here first. The first number on the Euler problem 3 is 13195. Checking for its prime was easy as pie but when i get to solve for bigger numbers, PHP was not able able to correctly give the result to the modulus part. i have to add BC math functions to it.

Since we will be testing large numbers for prime over and over it is important that our script is optimized and will never have to do unnecessary calculations like e.g. we all know that any number that is divisible by 2 is not a prime, well, except for 2 itself so we can omit it by incrementing the loop +2.

Right now, the largest know prime number is 257,885,161−1

Also, EFF will award $150,000 to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits.

Here is the prime checker script:

<?php
if(isprime(10)
  echo "true";
else 
  echo "false";

function isprime($n)
{
	if ($n == 1)
		return false;
	if ($n == 2)
		return true;
	if ($n%2 == 0)
		return false;
	for($i=3; $i <= ceil(bcsqrt($n)); $i+=2)
		if(bcmod($n,$i) == 0)
			return false;
	return true;
}
?>

 

Leave a Reply