Alright, so today we are going to compare two sets of code that do the exact same thing: generate prime numbers! Exciting, right? I use this example because my boss at one of the first software development companies I worked for gave me a challenge, to create a prime number generator in seven lines of code or less. I did so, and now its down to one line (kind of), but is it really the most efficient code? Not at all, but it does its job.

I also created another version of the code that runs much more efficiently, but it is significantly longer. Let's begin.

I want to start by showing you the one-line code and explaining it. Here's that code:

This one generates all prime numbers between 0 and 10000.

<?for($i=2;$i<10000;$i++){for($x=2;$i%$x!=0;$x++){echo$x==($i-1) ? $i." ":"";}}?>

Here's a little cleaner version of it to make it easier to read:

<?
for($i=2;$i<10000;$i++)
{
for($x=2;$i%$x!=0;$x++)
{
echo$x==($i-1) ? $i." ":"";
}
}
?>

Here is the code explained:

The first line:

<?

<?php

The second line:

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

The third line:

{

The fourth line:

for($x=2; $i%$x!=0; $x++)

The fifth line:

{

The sixth line:

echo $x == ($i-1) ? $i." ":"";

The seventh line:

}

The eighth line:

}

The ninth line:

?>

Now let's look at the Efficient version:

<?
$primes = array(2);
for($i=3; $i <= 10000; $i++)
{
foreach ($primes as $prime)
{
if ($i % $prime == 0)
{
break;
}
elseif ($prime >= sqrt($i))
{
$primes[] = $i;
break;
}
}
}
foreach ($primes as $prime) echo $prime." ";
?>

This one works a little differently:

Obviously the first line opens up the php code, the second line sets a variable

$primes = array(2);

The next line is

for($i=3; $i<10000; $i++)

Next we have

foreach ($primes as $prime)

Next we have

if ($i % $prime == 0)

The next line

elseif ($prime >= sqrt($i))

The reason we only test up to the square root is to save time, because every number larger than the square root that divides evenly into our $i will result in a number smaller than the square root if divided into it.  For example: the square root of 100 is 10, so numbers larger than 10 that divide into 100 (20, 25, 50) produce numbers smaller than the square root as answers (5, 4, 2 respectively).  So we would have found those answers in all the numbers we checked up to 10.  So by only checking through 10 you save all sorts of time.

Now the reason we are only testing prime numbers is also to save time, because every number factors down into prime numbers, for example let's again take 100:

factors are 2, 4, 5, 10, 20, 25, and 50.

2 and 5 are already prime,

4 gets broken back up into 2 and 2 which are prime,

10 gets broken up into 2 and 5 which are prime,

20 to 10 (already covered) 2, 4 (already covered) and 5,

25 to 5 and 5 which are prime

50 down into 2, 5, 10 (already covered), 25 (already covered)

So everything eventually gets broken down into 2 and/or 5 in this case, and I assure you every number that is not prime gets broken down into prime numbers at its root factors, so there is no need to test any numbers that aren't prime.

This program would test 2, 3, 5, and 7 on 100 (those are all the prime numbers less than its square root: 10).  So we didn't have to check 4, 6, 8, 9 or 10.  On larger numbers the savings is even greater.

Below is a chart showing how much faster the efficient version is than the one line version for 0 to different values:

As you can see the efficient one is faster from the start, but if the one line one was faster for the first part it'd probably be worth it to set the code to use the oneline for 0 - wherever the separation point is and then switch to the efficient version after that.

Alright, thats all I've got for you, until next time!