2013-05-12

8 mins

Recently I attended this months Seattle PHP meetup, where we were instructed to all bring our laptops as the night would be spent tackling some coding challenges they had prepared.

The table I sat at all decided to group up and decided to tackle on the simpler challenge, to generate as many prime numbers in one minute, as some of them were new to PHP. It may not have seemed to be cool or snazzy, but it's a great learning experience. I even learned a few things in the process which I'm always up for.

We decided to just simply go for a brute-force method. Obviously this won't generate as many prime numbers in one minute as some other methods, but it would be presented in a way that would be easy to decipher and read when going through the code.

Our first run did alright, generating a little more than 7,000 prime numbers:

```
<?php
function isPrime($n)
{
$i = 2;
if ($n == 2) {
return true;
}
while ($i < $n) {
if ($n % $i == 0) {
return false;
}
$i++;
}
return true;
}
$count = 0;
for ($i = 3; $i > 0; $i++) {
if (isPrime($i)) {
/*
$count++;
$file = "primes.txt";
$current = file_get_contents($file);
$current .= $i."n";
file_put_contents($file, $current);
*/
echo $i.' ';
flush();
ob_flush();
}
}
```

The code is messy, as we were kinda rushing it.

We were given some tips on how to optimize it a bit more, so we attempted to implement them in the time we had left before some of our group had to leave. Well, that led to some typo's in our code which broke it in the end. But we did manage to generate 2.3 million three's in one minute!

After I came home, I sat down with the code again and re-coded it cleaning it up and implementing some small optimizations:

```
<?php
/**
* Prime number generator contest
*
* Generate as many prime numbers within one minute of execution time.
*
* Definition:
* Prime numbers are the numbers that are bigger than one and cannot be divided
* evenly by any other number except 1 and itself.
*
* Conditions:
* (1): If a number can be divided evenly by any number except 1 and itself, it is not prime.
* (2): Prime numbers are whole numbers greater than 1.
* (3): 0 and 1 are not prime numbers.
* (4): 2 is a prime number.
*/
// Set our execution time limit to one minute
set_time_limit(60);
function is_prime($number)
{
// Let's do some simple checks first
// 1 is not a prime number
if($number == 1){ return FALSE; }
// 2 is a prime number
if($number == 2){ return TRUE; }
// If the number can be divided by 2 cleanly, then it's not a prime number
// (ie. it's an even number)
if($number % 2 == 0){ return FALSE; }
// I think we can safely assume it's quicker to start at 3
$divisor = 3;
// This is a very brute force method to determine if the provided number
// is a prime.
while($divisor < $number)
{
// We'll use the modulus arithmetic operator (%) to return the remainder
// of our two numbers
if($number % $divisor == 0)
{
// Uh oh! Looks like this is not a prime number
return FALSE;
}
// We'll increase our divisor by 2 to skip even numbers
// and to speed up the process of running through numbers.
$divisor = $divisor + 2;
}
// If we got this far, we haven't returned anything FALSE
// so it must be a prime number!
return TRUE;
}
// Now that we have our function that can check a number if it's prime or not,
// let's loop through some numbers to generate prime numbers on the fly.
// This will loop forever until the script times out.
for($number = 1; $number > 0; $number = $number + 2)
{
if(is_prime($number))
{
echo $number."n";
flush();
ob_flush();
}
}
```

Nice and pretty, no? This generated roughly more than 10,400 prime numbers. While this is better than our first attempt, there are still a few more things we can do to optimize the code significantly increasing it's output data.

First off, you will want to have a complete understanding of the subject at hand. In our case we want to know what prime numbers are in the first place, and what methods are there that we can use to calculate if a number is prime or not.

This is perhaps the most important tip in any undertaking. Do your research, and do it any way even if you think you know everything about the subject as I guarantee there is always something to be learned.

So let's consult our friend Google and look up "prime numbers".

Taken from Wolfram MathWorld:

A prime number (or prime integer, often simply called a "prime" for short) is a positive integer that has no positive integer divisors other than 1 and itself. [Source]

Great! We answered our first question. Seems simple enough, right? It's a number that can only be divided by itself and the number 1.

After a quick Google of our question, you'll come to find that there are quite a few ways to calculate if a number is prime or not. You'll also find that in our above code we used the division method, which also happens to be the most time consuming.

... take your number and try to divide it by 2, if not, then try 3, if not try 4, if not try 5. This can be time consuming and not something you would want to use with very large numbers. [Source]

So right away we see that the math in our script can be improved to cut down process time and increase output. In our above code we're essentially dividing our number by every number underneath it until we hit a condition that returns either TRUE or FALSE. The while loop will take it's longest to run through on large prime numbers, as it doesn't return TRUE until it's gone through every number beneath it.

There are a couple of shortcuts we can take to greatly improve this.

The first choice is, instead of trying to divide our number by every number underneath it, we can divide it by the prime numbers beneath it.

Only divide prime numbers that are smaller than the number you are testing as possible factors.

For example, let's see how this would play out for the number 37:

```
37 / 2 = 18.5 (2 is not a factor of 37)
37 / 3 = 12.3333~ (3 is not a factor of 37)
37 / 5 = 7.4 (5 is not a factor of 37)
37 / 7 = 5.3 (7 is not a factor of 37)
37 / 11 = 3.4 (11 is not a factor of 37)
37 / 13 = 2.8 (13 is not a factor of 37)
37 / 17 = 2.1 (17 is not a factor of 37)
37 / 19 = 1.9 (19 is not a factor of 37)
37 / 23 = 1.6 (23 is not a factor of 37)
37 / 29 = 1.3 (29 is not a factor of 37)
37 / 31 = 1.2 (31 is not a factor of 37)
```

This would greatly increase the number of prime numbers we could generate within one minute as this method would greatly decrease the number of loops we'd make on a number. So in the case of 37, we would be making only 11 loops instead of 36. That's more than half the numbers cut out that are just wasting processing time. So let's re-write our code with this new found knowledge!

```
<?php
/**
* Prime number generator contest
* Version 2
*
* Generate as many prime numbers within one minute of execution time.
*
* Definition:
* Prime numbers are the numbers that are bigger than one and cannot be divided
* evenly by any other number except 1 and itself.
*
* Conditions:
* (1): If a number can be divided evenly by any number except 1 and itself, it is not prime.
* (2): Prime numbers are whole numbers greater than 1.
* (3): 0 and 1 are not prime numbers.
* (4): 2 is a prime number.
*/
// Set our execution time limit to one minute
set_time_limit(60);
// Create an array to store our prime numbers
$prime_numbers = array();
// Let's loop through some numbers to generate prime numbers on the fly.
// This will loop forever until the script times out.
for($counter = 2; $counter > 0; $counter++)
{
// We'll set this to FALSE below if our test fails
$prime = TRUE;
// Here is where we loop through our previously generated prime numbers
foreach($prime_numbers as $divisor)
{
if($counter % $divisor == 0)
{
// Uh oh! Looks like this is not a prime number
$prime = FALSE;
break;
}
// Break the foreach loop if our prime number is larger than the
// number we're testing
if($divisor > $counter)
{
break;
}
}
if($prime)
{
// Hooray! It's a prime number. Let's add it to our prime numbers
// array and spit the number out
$prime_numbers[] = $counter;
echo $counter."n";
flush();
ob_flush();
}
}
```

After running this for one minute, we were able to generate over 20,700 prime numbers. Wow, with a small modification we were able to double our results. Impressive, but let's move on to our second choice, which builds off this one.

Choice three. What if I told you there was a way to cut the above method's loop more than half, again? Crazy you might say, yes, but it is possible and quite easy to do and implement. To do this, we simply need to retrieve the square root of our number.

If a number $n is not a prime, it can be factored into two factors $a and $b: $n = $a

$b If both $a and $b were greater than the square root of $n, $a$b would be greater than $n. So at least one of those factors must be less [than] or equal to the square root of $n, and to check if $n is prime, we only need to test for factors less than or equal to the square root [Source: Sven Marnach's answer]

So going with our example of 37 from before, we would simply need to go through the following:

```
The square root of 37 is 6.1
37 / 2 = 18.5 (2 is not a factor of 37)
37 / 3 = 12.3333~ (3 is not a factor of 37)
37 / 5 = 7.4 (5 is not a factor of 37)
```

We could then determine from there that nothing else would be a factor of 37, and come to a conclusion that 37 is a prime number. So we've effectively gone from 36, to 11, to now 3 loops.

With this in mind, we actually don't need to alter our above code that much to implement this.

```
<?php
/**
* Prime number generator contest
* Version 3
*
* Generate as many prime numbers within one minute of execution time.
*
* Definition:
* Prime numbers are the numbers that are bigger than one and cannot be divided
* evenly by any other number except 1 and itself.
*
* Conditions:
* (1): If a number can be divided evenly by any number except 1 and itself, it is not prime.
* (2): Prime numbers are whole numbers greater than 1.
* (3): 0 and 1 are not prime numbers.
* (4): 2 is a prime number.
*/
// Set our execution time limit to one minute
set_time_limit(60);
// Create an array to store our prime numbers
$prime_numbers = array();
// Let's loop through some numbers to generate prime numbers on the fly.
// This will loop forever until the script times out.
for($counter = 2; $counter > 0; $counter++)
{
// We'll create a variable to store the square root of our number
$square_root = sqrt($counter);
// We'll set this to FALSE below if our test fails
$prime = TRUE;
// Here is where we loop through our previously generated prime numbers
foreach($prime_numbers as $divisor)
{
if($counter % $divisor == 0)
{
// Uh oh! Looks like this is not a prime number
$prime = FALSE;
break;
}
// Break the foreach loop if our prime number is larger than the
// number's square root
if($divisor > $square_root)
{
break;
}
}
if($prime)
{
// Hooray! It's a prime number. Let's add it to our prime numbers
// array and spit the number out
$prime_numbers[] = $counter;
echo $counter."n";
flush();
ob_flush();
}
}
```

Yeah, go ahead and count the results. This should generate more than 384,400 prime numbers in one minute. All of the sudden our measly 7,000 is ridiculously unoptimized and slow.

Well this post certainly went longer than I initially anticipated. If you followed through to the end here, I hope you learned something new that you can apply to your own work. This should also go to show that even a simple challenge such as this can yield a great and invaluable learning experience when learning how to develop your own code, and I encourage everyone to seek out challenges like this and give your all to them.