Prime numbers between X and Y.

Small, short code snippets that other people may find useful. Do you have a good regex that you would like to share? Share it! Even better, the code can be commented on, and improved.

Moderator: General Moderators

Post Reply
User avatar
Verminox
Forum Contributor
Posts: 101
Joined: Sun May 07, 2006 5:19 am

Prime numbers between X and Y.

Post by Verminox »

Two reasons why this won't really appeal to you:
1.) This is a very basic function, nothing great in it.
2.) It may not seem very useful to you.

However, I want to share this function with you anyway so here goes:

Code: Select all

<?php
function get_primes($min,$max) {
    $primes = array();    
    for ( $x=$min; $x<=$max; $x++ ) {
        //$x is every number between$ min and $max. Main loop
        if ( $x == 2 ) { $primes[] = $x; } //2 is a prime
        for ( $i=2; $i<$x; $i++ ) {
            //$i is every integer such that 2<$i<$x 
            $remainder = ($x % $i);        
            if ( $remainder == 0 ) {
                $i = $x;   //Set $i=$x so that the loop reaches the end and goes on to next value of $x
                continue;  //Break current loop
            } else if ( $i == ($x-1) ) {
                $primes[] = $x;  //Means this is the largest value of $i. So if we reached this far the number is prime
            } else {
                //Do nothing, let the loop go on
            }
        }
    }
    return $primes;
}
?>

This function should return primes between X and Y.

Example:

Code: Select all

<?php
$primes = get_primes(2,30);
foreach($primes as $prime){
	echo $prime."\n";
}
?>
This should output:

Code: Select all

2
3
5
7
11
13
17
19
23
29
Charles256
DevNet Resident
Posts: 1375
Joined: Fri Sep 16, 2005 9:06 pm

Post by Charles256 »

okay..my function..

Code: Select all

function prime($min,$max)
{
  $prime=array();
  for ($i=$min;$i<=$max;$i++)
  {
    $count=0;
    for ($p=1;$p<=$i;$p++)
    {
      if ($i%$p==0)
      {
        $count++;
      }
      if ($count>2)
      {
        break;
      }
    }
    if ($count==2)
    {
      $prime[]=$i;
    }
  }
  return $prime;
}
does the same thing. I just think it reads better. on another note. you're function is faster..not entirely sure why :-D not by much, just enough to bug me
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post by timvw »

Charles, you could start your loop at 2 (instead of 1) and just break as soon as you find another number x where % x == 0

At http://en.wikipedia.org/wiki/Prime_number there are couple of faster algorithms mentionned...
Charles256
DevNet Resident
Posts: 1375
Joined: Fri Sep 16, 2005 9:06 pm

Post by Charles256 »

in reply to your post i bit the hell out of my tongue..owie..good point though :-D
User avatar
Verminox
Forum Contributor
Posts: 101
Joined: Sun May 07, 2006 5:19 am

Post by Verminox »

In the end it will just come back to something like my function. Also, I don't use a variable $count at all so that may be saving some time (I don't know much about speed optmization so I'm not sure if it would make any difference though).
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post by timvw »

Your "for ( $i=2; $i<$x; $i++ )" loop can be optimised to "$sqrt = sqrt($x); for ($i = 2; $i < $sqrt; ++$i)"..

Assuming the user requests primes between a and b, this interval is x numbers large, your code can skip 'x times sqrt(b)' tests if the module is 0.
User avatar
Verminox
Forum Contributor
Posts: 101
Joined: Sun May 07, 2006 5:19 am

Post by Verminox »

timvw wrote:Your "for ( $i=2; $i<$x; $i++ )" loop can be optimised to "$sqrt = sqrt($x); for ($i = 2; $i < $sqrt; ++$i)"..

Assuming the user requests primes between a and b, this interval is x numbers large, your code can skip 'x times sqrt(b)' tests if the module is 0.

To tell you the truth, I did not get you. Could you explain a bit more with the square root thing?
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post by timvw »

Verminox wrote: To tell you the truth, I did not get you. Could you explain a bit more with the square root thing?
In case x is not a prime (thus a composite) then x can be factored in two numbers and at least one of these numbers is less than or equal to square (x).

Proof:

- We assume that x is not a prime, but composed by two numbers, name them v and w (thus x = v * w)
- We assume that both numbers are larger than square(x) (thus v > sqrt(x) and w > sqrt(x))

We know that v > sqrt(x) and w > sqrt(x)
=> v * w > sqrt(x) * sqrt(x)
=> v * w > x !!! impossibility

Therefor, the assumption that both v and w are larger than sqrt(x) cannot be true.
User avatar
Verminox
Forum Contributor
Posts: 101
Joined: Sun May 07, 2006 5:19 am

Post by Verminox »

Oh I see now, I read your post as 'square' or something which got me really confused. I understand now.

So I can change :

Code: Select all

for ( $i=2; $i<$x; $i++ )
To:

Code: Select all

for ( $i=2; $i<sqrt($x); $i++ )

Smart indeed. :)
User avatar
kaszu
Forum Regular
Posts: 749
Joined: Wed Jul 19, 2006 7:29 am

Post by kaszu »

feyd | Please use

Code: Select all

,

Code: Select all

and [syntax="..."] tags where appropriate when posting code. Your post has been edited to reflect how we'd like it posted. Please read:  [url=http://forums.devnetwork.net/viewtopic.php?t=21171]Posting Code in the Forums[/url] to learn how to do it too.[/color]


Hi here is my function, BUT it doesn't have minimum value!!!
It's faster than previous 2 functions, even when max is 5000 and minimum (not for this function) is 2500, but if (max - min) is small, then this function will be much slower.

It's checking if x is dividing with other prime numbers, not will all numbers until x

Code: Select all

function get_primes_my($max)
{
	$primes = Array();
	$primes[] = 2;
	
	for($x = 2; $x < $max; $x++)
	{
		$i = true;
		$sx = sqrt($x);
		$primes2 = $primes;
		while((list(,$prime) = each($primes2)) and ($i == true))
		{
			$remainder = ($x % $prime); 
			
			if ( $remainder == 0 ) {
				//$i = false;
				continue(2);
            		} else if ( $prime > $sx  ) {
            			$primes[] = $x;
            			//$i = false;
            			continue(2);
			}
		}
	}
	return $primes;
}
Hope you like it :)


feyd | Please use

Code: Select all

,

Code: Select all

and [syntax="..."] tags where appropriate when posting code. Your post has been edited to reflect how we'd like it posted. Please read:  [url=http://forums.devnetwork.net/viewtopic.php?t=21171]Posting Code in the Forums[/url] to learn how to do it too.[/color]
diegoide
Forum Newbie
Posts: 1
Joined: Tue Aug 08, 2006 2:21 pm

Post by diegoide »

hi.. this is my first post :-)

I think you can exclude the even numbers to optimize more the code ;-)
the first loop can be something like this

Code: Select all

for ($i=$min;$i<=$max;$i+=2)

if $min is odd . If not, you can begin with the next odd number with $i=$min+1
User avatar
Verminox
Forum Contributor
Posts: 101
Joined: Sun May 07, 2006 5:19 am

Post by Verminox »

Good idea but it would be better done this way:

Code: Select all

<?php
function get_primes($min,$max) {
    $primes = array();   
    for ( $x=$min; $x<=$max; $x++ ) {
        //$x is every number between$ min and $max. Main loop
        if ( $x == 2 ) {
                $primes[] = $x; //2 is a prime
        } else if ( $x % 2 == 0 ) { //Even number greater than 2
                continue; //Break Loop
        } 
        for ( $i=2; $i<$x; $i++ ) {
            //$i is every integer such that 2<$i<$x
            $remainder = ($x % $i);       
            if ( $remainder == 0 ) {
                $i = $x;   //Set $i=$x so that the loop reaches the end and goes on to next value of $x
                continue;  //Break current loop
            } else if ( $i == ($x-1) ) {
                $primes[] = $x;  //Means this is the largest value of $i. So if we reached this far the number is prime
            } else {
                //Do nothing, let the loop go on
            }
        }
    }
	return $primes;
}
?>


Edit: Well I guess this isn't any better than your idea digoide, either will work fine. And this function is so small and trivial that I don't think anybody would even want to optimize it any more.
Post Reply