Prime Time

12 08 2010

Yesterday, I read somewhere online that there are programmers with such poor programming skills that they are unable to write code that would display prime numbers between zero and a hundred. While I have written a lot of code, I knew that was one application I had yet to write. At the same time, I could visualize being at an interview where someone on the panel requests that I go to a whiteboard and write out that kind of code in PHP and to use recursion, too. So, I came up with the following code, before checking to see other online solutions:

$numArray = range(2,100);
$n = 0;

function factor($num, $div=1 ) {
    if ( $div == 1) {
         return $num;       // . ' ' .$div;
	if ($num % $div == 0 && $div > 1) {
		return ' ';    // "$num not prime";
	if ($num % $div)
		echo factor( $num,$div );

for ($i=0, $max=count($numArray); $i < $max; $i++)
    $n = $numArray[ $i ];         
     echo factor( $n, $n-1 ) . ' ';

When I ran the code it correctly yielded the following result:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

To solve the problem, one must of course understand what a prime number is. It is a number greater than one whose only divisors are the number itself and 1. According to

Primes are applied in several routines in information technology, such as public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors.

There is another approach that I read about at same Wikipedia url which suggests creating a sieve to find prime numbers. The url shows a JAVA code example which creates a “Sieve of Eratosthenes” to flush out everything but the primes. I’ve adapated that example for PHP, as follows:

$n = 100;

function generatePrime( $n )
		$list = range(2,$n);
                // Initially, let p equal 2, the first prime number.
		$p = 2; 
                $k = 0; // k keeps track of the index of the current prime 
         // Repeat until $p squared  is greater than $n.
		while( $p*$p < $n )
                        for( $i = $k+1; $i < count($list); $i++ ) {
				if( $list[$i] % $p == 0 ) { 
				  unset($list[$i]);        // remove non-prime
				  $list = array_values($list); // reindex
  			$p = $list[$k++];
                // All the remaining numbers in the list are prime
                for( $i = 0, $size=count($list); $i < $size; $i++ ) {
					echo  '<span style="color:blue">' . $list[$i] . " " ;

generatePrime( $n );

With this last method, we are essentially picking off numbers that are multiples of 2s, 3s, etc. until the square of the next prime number is greater than the maximum value of the numerical range, 100 in this case. This method may be less intuitive than the first example. However, there is no slow down due to recursion; it is far faster than the first example. The Wikipedia article referenced above also cautions that the last example is “useful for relatively small primes. ”

This work is licensed under a Creative Commons License




Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: