prime number function 1

[dingleberry]

I was bored about a week ago and that got me to thinking. I did not know of a function to calculate prime numbers (and there might be one but I couldn't find it.) I decided to write one. Basically it starts with a range of numbers (10000) and starts at 1. It takes every number up to that number and runs a fmod function on it to determine if there is any remainder. You can imagine however that this function is wildly resourse intensive as the number increases because if for instance the number is 1111, the computer needs to calculate 1111/1 (match) and 1111/2 (no match) and 1111/3 (no match) etc until it get's more than 2 matches and then the loop exits and the number goes to 1112 and it starts all over again. To make this function lean as possible I've added a few immediate checks to kill the loop if true such as if the number is even we know it's not a prime and if the sum of the numbers of the number equals nine we know it's divisible by nine so that kills the loop (for instance 2322 -- 2+3+2+2=9 so 2322/9 is 258.) Also because we know the numerator is odd due to the fact that the function immediately throws out even numbers so that if the demoninator is even, we increase the denominator by 1 to make it odd because an odd divided by an even will always have a remainder.

I'm looking for some more tests to run to kill this loop if true or false. Any suggestions appreciated.

Another issue is my install of php does not include the str_split function and I don't know why so I had to write one at the bottom of the program and call that. Anyone know why str_split is not a valid function in my situation? Is that part of a library or something I did not compile with?

I've attached the program below. Use it if you want and modify it as you see fit but let me know what you do to make this more efficient. Currently I can only run about 5450 numbers before the 30 second timeout occurs. My goal would be to get it to 10000 or higher.

<?


$number = 10000;
$x = 1;
$count=0;
$y=1;
$g=2;


while ($x <= $number)
{
$even=fmod($x, $g);
if ($even==0)
{
# this means that we have an even numerator so count goes to three to disrupt following while loop.
$count=3;
}
else if (array_sum(str_split($x))==9)
{
$count=3;
# this means that the sum of the integers of the number is nine which means it's divisable by nine.
}

while (($count<=2) && ($y<=$x))
{
$yeven = fmod($y, $g);
if ($yeven==0)
{
# this means that the denominator is even in the equation and because we know that our numerator is odd due to the last loop, we can exclude it.
# echo "for $x we bombed here because y is $y<br>";
$y++;
}
$z=fmod($x, $y);
if ($z==0)
{
$y++;
$count++;
}
else if ($z<>0)
{
$y++;
}
}
if ($count <= 2)
{
echo "$x is a prime<br>";
}
$count=0;
$y=1;
$x++;
}


function str_split($split_length)
{
preg_match_all('/.{1,' . $split_length . '}/s', $string, $matches);

return $matches[0];
}

?>


Thanks,
Dan

 

[DRJ478]

1. str_split is implemented only in PHP 5 and up
2. You can always return to the top of the current loop by using continue

 

[DRJ478]

More:
You can stop the outer most loop at the first number that is larger than the square root of the number you are testing.

The Sieve of Eratosthenes uses a different concept - upside down. Instead of marking primes it marks the multiples of the numbers in the range looked at. All number remaining unmarked are prime.
This method is much faster. Try to implement it and you'll see.

 

[dingleberry]

thanks a lot... that's a great idea. I'll try to reprogram to accomodate for that.

 

[skiflyer]

I've been out of school for a few years now, and it's 3 am, so forgive my mistakes...

First things first... the Sieve mentioned above is much more efficient... but if you wanted to optimize what's there.

Why are you looking for $count >= 2?

And also, why bother with the even tests? Seems to me like you're wasting operations.

I would think like so...
for each number, start dividing by 2, not 1. And as soon as you get a result with no remainder, you can quit. Evens are caught immediately so they no longer need to be a special case.

Also you can stop at x/2 if you divide by all numbers and not just odds, because no non-prime number has its minimum factor > x/2. Actually I think no odd non-prime number has its minimum odd factor > x/2, but I'm not positive about that one.

And as mentioned above, the continue will let you break the loop and skip several comparisons... comparisons are expensive.

 

[skiflyer]

Yeah I can't sleep, so I just implemented some of those changes, and saved over 50%.

Also, I switched from a while loop to a for loop, and the good old fashioned switch from $x++ to ++$x

<?php


$number = 10000;
$x = 1;
$count=0;
$y=1;
$primes = 0;

$time1=microtime_float(true);




for ($x=3;$x<=$number;++$x)
{
	$prime=true;
	$half_x = (int) $x/2;
	$y = 2;

	if (array_sum(str_split($x))==9)
        {
        	$prime=false;
//               this means that the sum of the integers of the number is nine which means it's divisable by nine.
        }

        while ($prime && $y < $half_x)
        {
          $z=fmod($x, $y);
          if ($z==0)
          {
            $prime=false;
          }
	  ++$y;
	}
        
	if ($prime) 
	{
		++$primes;
		echo "$x is a prime<br />";
	}
}
$time2=microtime_float(true);

echo $time1.':::'.$time2;
echo '<hr>';
echo $time2-$time1.' to find '.$primes.' primes';

function microtime_float()
{
   list($usec, $sec) = explode(" ", microtime());
   return ((float)$usec + (float)$sec);
} 

function str_split($split_length)
{
        preg_match_all('/.{1,' . $split_length . '}/s', $string, $matches);

        return $matches[0];
}

?>

 

[dingleberry]

wow! very cool. I wasn't aware ++$x and $x++ were different. Can you explain? Great suggestions on the math too.

 

[ericbrunson]

dingleberry:

$x++ and ++$x are post-increment and pre-increment. The first uses the value of $x then adds one to it, the second increments it first.

You are aware that you only have to test divisibility by all prime numbers less than or equal to the square root of the number you are testing, aren't you? Add each prime number you have found to an array, then you only have to iterate over that array when testing any subsequent integer. That would take your looping down an order of magnitude.

You'd probably be interested in reading a book on number theory. This problem, though interesting from a learning standpoint, has been done to extremes.

 

[ericbrunson]

P.S.
I'll bet you dividing by three is faster than exploding the string and summing the digits. After all, if it's divisible by nine, it's divisible by three. Going back to my previous post, you only have to test divisibility by prime numbers and 9 is not prime.

And this is why a major in math is cooler than a major in CS. ;-)

 

[skiflyer]

square root! not half, woops... that'll speed it up significantly more.

And yeah, it's post vs. pre increment as ericbrunson mentioned. That actually makes the behavior different in certain applications, but in an application like the above, it makes no functional difference. It's an old C optimization trick to use pre rather than post where possible. I don't know if that actually translates to PHP or not, but given that it runs on C (or is it C++) underneath, and given that it's not compiled so there's no chance for it to be done for you as it usually is in C and C++ now adays, I figure why not use it where appropriate.

Yeah, the 9 test can't be helping things at all... 3 is the second number checked, so you're adding 1 rather expensive operation on every number to save 1 comparitevely inexpensive step on every 9th number.

 

[ArkM]

Before (or even after Inventing of the Wheels see useful links:

http://primes.utm.edu/index.html

 

[dingleberry]

Hey ArkM,

Good stuff. I'm only doing this for fun. Not trying to come up with some new mathmatical model however if I did, that'd be pretty cool too. Prime numbers are mysterious and I like mysteries. That's all.

Great link though. Full of some good stuff.

I'm currently revising script to incorporate some of the above changes. I'll test for efficiency and update when completed.

dan

 

[dingleberry]

sky,

you're suggesting that I can stop dividing at the square root of the number being tested?

So no non prime number has it's min factor > $x^.5?

Thanks,
dan

 

[skiflyer]

Yes, that's true... but ericbrunson is the one who pointed that out, I mistakingly said x/2... but yes it's x^.5

 

[DRJ478]

Sorry, but I have to claim responsibility for the square root suggestion. Just read my second post.

 

[skiflyer]

Heh, I need sleep!

 

[dingleberry]

DRJ478 that works great! Sorry about the credit snafu. Ski, I used your code as the base for the new function and listed it below. I also added a front end to it for people to enter a range of numbers and check a box if they want to see the math. I have attached it below:

<?php

(int) $high = $_POST['high'];
(int) $low = $_POST['low'];
$show=$_POST['show'];

if (!isset($high))
{
echo "

Prime Number Calculator:
<p>Enter a low range and a high range and this will determine the prime numbers between them.</p>
<p>If you want to check for one number enter it as both low and high. </p>
<p>If you find an errer in this calculator or have any suggestions, I'd appreciate feedback.</p>

<form action=\"index.php\" method=\"post\" name=\"range\" id=\"range\">
<p>Please Enter a range
<input name=\"low\" type=\"text\" id=\"low\" size=\"10\" maxlength=\"10\">
(low range) to
<input name=\"high\" type=\"text\" id=\"high\" size=\"10\" maxlength=\"10\">
(high range)</p>
<p>If you would like to see the specifics (much slower) of the math check this box
<input name=\"show\" type=\"checkbox\" id=\"show\" value=\"show\">
</p>
<p>
<input type=\"submit\" name=\"Submit\" value=\"Submit\">
</p>
</form>
";
exit;
}


$y=1;
$primes = 0;
$three=3;

$time1=microtime_float(true);

for ($x=$low;$x<=$high;++$x)
{
$prime=true;
$sqrt_x = sqrt($x);
$y = 2;

if ((fmod($x, $three)==0) && ($x<>3))
{
if ($show=="show")
{
echo "<hr><b>$x is not prime because it's divisable by 3</b><br>";
}
$prime=false;
}

while ($prime && $y <= $sqrt_x)
{
$z=fmod($x, $y);
if ($show=="show") {
echo "<hr>for x=$x and y=$y the remainder of $x/$y is $z<br>";
}
if ($z==0)
{
if ($show=="show")
{
echo "<b>$x is not a prime</b><br>";
}
$prime=false;
}
++$y;
}

if ($prime)
{
++$primes;
echo "<hr><b>$x is a prime</b><br />";
}
}
$time2=microtime_float(true);

echo '<hr>';
echo $time2-$time1.'seconds to find '.$primes.' primes';


function microtime_float()
{
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}
?>

If you want to see it in action go to

http://www.theorangestudio.com/prime.php

Also if you want to modify it or have any ideas to make it even faster, let me know! Thanks a lot everyone!
dan

 

[ericbrunson]

Again, you only need to test divisibility by prime numbers. There's no point it testing if 2983748 is divisible by 12 since if it were, it'd be divisible by 2, 3 and 6, which you've already tested.

 

[DeCap]

This should do the job.

I wrote it as an include file "primes_inc.php".

First prime numbers are "hard coded" up to 100. The procedures extend (function "extend_primes") this table as needed if you ask numbers above "10,000".

These functions check only modulos by prime numbers up to the square root as already suggested.

I think there are not many ways to be more efficient. The only way should be to extend the hard coded $prime_number array to the square root of the highest value you are likely to use.

Functions defined :

is_prime( $n, $debug )
-------------------
$n : number to be checked
$debug : when set on 1 some debugging messages displayed
result : 0 (not prime) or 1 (is prime).

primes( $n, $debug )
------------------
$n : number from which you want to get the prime numbers
$debug : when set on 1 some debugging messages displayed
result : prime numbers of "$n" in a "|" separated string.

------
<?PHP
global $prime_number;

array( $prime_number );

$prime_number[] = 1;
$prime_number[] = 2;
$prime_number[] = 3;
$prime_number[] = 5;
$prime_number[] = 7;
$prime_number[] = 11;
$prime_number[] = 13;
$prime_number[] = 17;
$prime_number[] = 19;
$prime_number[] = 23;
$prime_number[] = 29;
$prime_number[] = 31;
$prime_number[] = 37;
$prime_number[] = 41;
$prime_number[] = 43;
$prime_number[] = 47;
$prime_number[] = 53;
$prime_number[] = 59;
$prime_number[] = 61;
$prime_number[] = 67;
$prime_number[] = 71;
$prime_number[] = 73;
$prime_number[] = 79;
$prime_number[] = 83;
$prime_number[] = 89;
$prime_number[] = 97;

function extend_primes( $n, $debug )
{
global $prime_number;

$nbr_primes = count( $prime_number );
$last_prime = $prime_number[$nbr_primes - 1];

for( $i = $last_prime + 2; $last_prime < $n; $i += 2 )
{
if( is_prime( $i, $debug ) )
{
$prime_number[] = $i;
$last_prime = $i;
if( $debug )
echo( "Primes extended to ".$i.".<br>" );
}
}

return( $result );
}

function is_prime( $n, $debug )
{
global $prime_number;

$is_not_prime = 0;

$root = floor( sqrt( $n ) );
$nbr_primes = count( $prime_number );
$last_prime = $prime_number[$nbr_primes - 1];
if( $debug )
echo( "Number of known prime number is ".$nbr_primes." and the last one is ".$last_prime.".<br>" );

if( $root <= $last_prime )
{
if( $debug )
echo( "Square root (".$root.") is lower than ".$last_prime." just scan prime_number array up to ".$root.".<br>" );

for( $i = 1; ($i < $nbr_primes) && ($root >= $prime_number[$i]) && !$is_not_prime; $i++ )
{
if( $debug )
echo( " ".$i.":".$prime_number[$i] );
$is_not_prime = ( ($n % $prime_number[$i]) == 0 );
}
if( $debug )
echo( "<br>" );
}
else
{
if( $debug )
echo( $root." is greater than ".$last_prime." extend primes.<br>" );

extend_primes( $root, $debug );
return( is_prime( $n, $debug ) );
}

$result = !$is_not_prime;
return( $result );
}

function primes( $n, $debug )
{
if( is_prime( $n, $debug ) )
$result = $n;
else
{
$result = "";
$first_item = 1;
for( $i = 2; $n != 1; $i++ )
{
if( is_prime( $i, $debug ) )
{
while( ($n % $i) == 0 )
{
if( !$first_item )
$result .= "|";
else
$first_item = 0;
$result .= $i;
$n /= $i;
}
}
}
}
return( $result );
}
?>
------

You can see the result of

------
<?PHP
include( "Includes/primes_inc.php" );

for( $i = 0, $j = 0; $j < 1000; $j++ )
{
if( is_prime( $j ) )
{
echo( $j."<br>" );
$i++;
}
else
{
echo( $j." = ".str_replace( "|", " * ", primes( $j ) ) ."<br>");
}
}
?>
------

on URL

http://denis.capart.free.fr/php/prime_numbers.php

(in the evening this free provider's servers are not very performant, consider to try this on your own server).

Hope this can help.

 

[DeCap]

Sorry, I made a little mistake in the example, I forgot "$debug" argument in the call of the functions !!! ((=:

I also forgot to say that "primes" function could be improved based on the hard coded primes table. I'll try to do it in a near future... if none of you does !!! (=;

------
<?PHP
include( "Includes/primes_inc.php" );

if( $debug = "" )
$debug = 0;

for( $i = 0, $j = 0; $j < 1000; $j++ )
{
    if( is_prime( $j, $debug ) )
    {
        echo( $j."<br>" );
        $i++;
    }
    else
    {
        echo( $j." = ".str_replace( "|", " * ", primes( $j, $debug ) ) ."<br>");
    }
}
?>
------