Finding prime numbers in php

I decided to take it upon myself to find all the prime numbers between 1 and 10,000. The first algorithm I was was by brute force, and the prime number php code is as follows:

# check to see if a number n is prime

# first divide number by 2, 3, 4, … n-2 and see if there is a modulus. If there is, then the number is not prime.

# regular way of finding prime numbers

for ($n=2; $n<10000; $n++)

{

$count=0;

for($i=2; $i<$n-1; $i++)

{

$k=$n%$i;

if ($k==0)

$count++;

}

if ($count==0)

echo “$n, “;

}

This code will echo all the prime numbers between 1 and 10,000. When I ran this script, it took about 16 seconds! This is way too long, so I tried to implement another prime number algorithm by using php. This time, I would not simply divide the number under test by EVERY integer smaller than it, but instead only by the numbers smaller than the square root. The code is as follows:

# using square root method. Only divide n up to sqrt(n) took .3 seconds for 10,000

for ($n=2; $n<10000; $n++)

{

$count=0;

$j=sqrt($n)+1;

for($i=2; $i<$j; $i++)

{

$k=$n%$i;

if ($k==0)

$count++;

}

if ($n==2)

echo “2, “;

if ($count==0)

echo “$n, “;

}

This time around, it took only .6 seconds!

Leave a Reply

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

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>