jump to navigation

Check for prime numbers with PHP January 7, 2011

Posted by Tournas Dimitrios in PHP.
trackback

Mathematicians have been fascinated by prime numbers for thousands of years. In fact, Eratosthenes (275-194 BC, Greece), devised a “sieve” to discover prime numbers. A sieve is like a strainer that you drain spaghetti through when it is done cooking. The water drains out, leaving your spaghetti behind. Well, Eratosthenes’s sieve drains out composite numbers and leaves prime numbers behind.

An infinitude of prime numbers exists, as demonstrated by Euclid around 300 BC

Before we talk about prime numbers,  I want to review some multiplication vocabulary with you…

Let’s look at the multiplication problem 5 x 6 = 30. The 5 and 6 are called factors. They are the numbers we multiply together to get the answer 30, which is called the product. 30 is also called a multiple of 5 because it is a product of 5 and another number, 6. 30 is also a multiple of 6 because it is the product of 6 and 5. The number 5 has many other multiples, like 10, 15, 20, 25, 35, 40, etc. The number 6 also has many other multiples, like 12, 18, 24, 36, 42, etc. Notice,  that multiples are the “times tables” for a number. 30 is a multiple of not only 5 and 6, but also of 2 (2×15), 3 (3×10), 10, and 15.

A prime numbers is a number greater than one whose factors are only one and itself. In other words, 6 is not prime, because its factors are 1, 2, 3, and 6 (1×6, 2×3). But 5 is prime, because the only way you can get a product of 5 is by multiplying 1 and 5 (1×5).

Composite numbers are all the other positive numbers greater than one. 6 is composite.

Lets apply a few  php script – lines to discover prime numbers :

The IsPrime() function uses the recursive method to check if a number is prime. It’s a fast function which can compute thousands of numbers within seconds.

<?php
 // Checks for prime numbers

     function IsPrime($num) {	 
     $No = 0 ;
	 $Result  = 0 ; 
    for($Divisor = 2 ; $Divisor < $num; $Divisor++) {
    $Result = $num / $Divisor ;	
    if($Result != 1 && intval($Result) == $Result) { 
	$No = 1 ;
	break ; 
			} 
       } // End of  loop		   		
    if($No != 1  )  {
	$Result = $num ; 
    }
     $No = 0;
 // If the only divisor is the number itself, it's prime 
	 return ($Result == $num) ? 'Yes' : 'No' ; 
      }  // End function 	

for($i = 0; $i < 100; $i++) {
echo "<b> Testing number $i  : </b>"  ; 
echo $i." is a prime number? ". IsPrime($i)."<br />";
      }

  ?>

Mathematicians are always trying to find large prime numbers. There are an infinite number of prime numbers, but they always want to know what the next largest one is that can be written down. They have found so many prime numbers now that only computers have the time and energy to look for the next highest prime number. In fact, the newest prime number is 420,921 digits long! If you want to see what it looks like, go to: >>>>>

Comments»

1. Franci - December 15, 2012

hi,

thanks for the script. it works great.
but can you please explain the script a little bit more, why some variables are put in it and why are some loops?

thanks

tournasdimitrios1 - December 16, 2012

@Franci
The code , as it was presented (with two loops) was inefficient and just confused the reader . I changed the code , this time only one loop is used .
The following code (which uses two loops) can be used to better understand this article . When code is more expressive than 1000 words , let it do it’s job .

<?php
 // Checks for prime numbers
     function IsPrime($Num) {	 
     $No = 0 ;
	 $Result  = 0 ; 
	 $skipLoopTwo = true ; 
	 $startNewLoopTwo = true ; 
    for($CurrNum = 2 ; $CurrNum <= $Num ; $CurrNum++) {
	echo "<h4>First loop  \$CurrNum  =  $CurrNum</h4> "  ; 
	if($startNewLoopTwo) echo '--------------- A new Second loop was started ------------- <br>' ; 
    for($Divisor = 2; $Divisor < $CurrNum; $Divisor++){
	$startNewLoopTwo = false ; 
	$skipLoopTwo = false ; 
    $Result = $CurrNum / $Divisor ;	
	echo "Second loop  \$CurrNum = $CurrNum , \$Divisor = $Divisor and \$Result is : $Result" . '<br>'  ; 
					$startNewLoopTwo = true ; 
    if($Result != 1 && intval($Result) == $Result){ 
	$No = 1;
	echo 'Integer number detected and <b>break-out-of-LoopTwo</b> is triggered  ...... \$Result is  ' .  $Result . '<br>'  ; 
	break ; 
			} 
       } // End of second loop	
	   			$startNewLopTwo = true ; 
    if($No != 1  )  {
	$msg1 = 'Second loop wasn\t executed  due to : \$Divisor < \$CurrNum <br>' ; 
	$msg2 = 'LoopTwo has reached his end , still no "INTEGER"  detected <br>' ; 
	$Result = $CurrNum ; 
	echo ($skipLoopTwo) ? $msg1  : $msg2 ;
    }
     $No = 0;
	 echo '--------------Exit second loop  , First loop will take action now ----------------- <br>' ; 
      } // End of first loop
 // If the only divisor is the number itself, it's prime 
	 echo 'END OF FIRST LOOP -- EVALUATE RESULT ----> ' ; 
	 return ($Result == $Num) ? 1 : 0 ; 
      } // End function 
	
$number = 47 ; 
echo "<h1> Testing number $number </h1>"  ; 
echo " is a prime number? ".IsPrime($number)."<br />";
 
 

Did I had underestimated the power of words ?
Let’s give to words a try : If the only divisor is the number itself, it’s prime .

Thanks for commenting on this Blog , have a nice day .

2. asd - February 4, 2014

So Bad


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s