Prime Numbers In Php

[SChaput]

Hello All,

I am in the process of trying to write this little script to find two prime numbers that equal any given number. For instance, if i run the function with the following command, findprimenumbers(100) it would spit out 87 and 13. Obviously this is going to require a certain number of nested loops, but get lost in really determining the number of loops as well as how exactly to store the data.

So far i've got the isPrime() function.


function isPrime($number)
{
if ($number < 2) {
return false;
}
for ($i=2; $i<=($number / 2); $i++) {
if($number % $i == 0) {
return false;
}
}
return true;
}


So i guess i have to have another function loop through all the numbres from 1 -> 100 and store the prime ones, then figure out whats equal to 100?

Can anyone shed any light on this? Thanks alot.

[BLiZZaRD]

Wouldn't it be easier to set the known primes in an array and just check a true or false? Or is this meant to go far beyond 100?

[djr33]

Is this a homework assignment? It sounds like it might be. Typically we don't answer homework assignment questions, or at least we'll only offer guidance. This is because learning occurs when you're doing the work, not when we're doing it for you.

But giving you the benefit of the doubt, here's some input:

For the function you've written that is correct, but there's another way to go about it that will be a bit faster/more efficient.
Dividing the number by 2 seems like the logical approach. But there's actually a way to avoid those calculations. When you check that 2 doesn't go into it, then you know that $n/2 is not a factor either. BUT also when you know that 3 doesn't go into it, then you also know that $n/3 is not a prime. In this way you can eliminate the chance much faster:
for ($i=2; $i<=ceil($number / $i); $i++) {
I also used ceil() to avoid any odd rounding issues where a fraction of the number might cause problems. It's unlikely this will ever be a problem but I can't think that far ahead without working out some complex math-- leaving that will be safer. It certainly won't hurt anything (except slight efficiency).

So now you need to find two numbers that give true from isPrime() and that add up to the whole, right?

Create your function findprimenumbers($n) so that:
1. You loop through from 2* through ($n-$i), using the same logic as above.
(Do you consider 1 a prime? 1+5=6, so that's a pair for 6?)
2. Within that loop, check if the generated number isPrime().
3. If it is prime, then subtract it from $n-- $n-$i=$j.
4. Check if $j isPrime()
5. If so, then you have found two primes that add up to it. Return these values/true.
6. Once you hit the highest numbers possible ($n-$i), then return false-- there is no pair like that.

[SChaput]

Edit:
Saw DJR33's post at the same time i posted the below. Will look into what he mentioned for my findprimenumbers and post back here.

Thanks.


Well, its going between 4 and 300. I took what you said and have generated the code below,


<?php
function IsPrime($number)
{
if ($number < 2) {
return false;
}
for ($i=2; $i<=($number / 2); $i++) {
if($number % $i == 0) {
return false;
}
}
return true;
}


$start = 0;
$end = 300;
$knownprimes = array();


while($start <= $end)
{

$check = IsPrime($start);

if($check == 1)
{
$knownprimes[] = $start;
}
$start++;

}


This puts all known primes into an array knownprimes.

But i guess my biggest issue is how can i search that array for two numbers that equal 4-300?

[djr33]

You can use an array, but if the numbers are going to vary a lot it'll be more efficient to skip that, probably. Efficiency is complex, and it's probably not worth worrying about for now. The array can certainly work if you like that method. You'll still need all the other logic, though-- this is just pre-processed.

Also, there's really no reason to use the variable "$check".
Just do:
if (isPrime($start)) { ... } else { ... }

[BLiZZaRD]

I would do it backwards, but that is just me... get the 2 numbers from the math, then check if they are both prime, if yes, jackpot, if no, then try again loser. But maybe I don't follow your specific needs either, so I will leave it to Daniel. :)

[djr33]

I think they're about the same efficiency, really doing the same thing just from different angles.

[SChaput]

Edit:
To View the output now:
http://ihatemyroommate.net/chaput3.php
Note: it may stop working since i'm working with it now.


Great guys, thanks alot for all of your options. I've got a nice block of code that is doing what i want it to, i THINK.

For testing purposes i have it output the number that two primes need to equal and a 1 if its found, and nothing if its not found. However, its outputting nothing for 4 and 6. Which, unless i'm mistaken are 2+2 and 3+3.

Any ideas?


here is the code:


<?php
function IsPrime($number)
{
if ($number < 2) {
return false;
}
for ($i=2; $i<=($number / 2); $i++) {
if($number % $i == 0) {
return false;
}
}
return true;
}





function findprimenumbers($n)

{
$base = 1;

while($base < ($n/2))
{
$check = IsPrime($base);

if($check == 1) //base is prime
{
$next = $n-$base;
$checkNext = IsPrime($next);
if($checkNext == 1){
return true;
break 1;
}

}


$base++;
}
return false;

}


$start = 4;
$end = 300;

while($start<=$end){

$do = findprimenumbers($start);
echo $start;
echo "-";
echo $do;
echo "<br>";

$start = $start + 2;
}

[djr33]

Ah, that makes sense. The numbers are the same.
This is the problem:
while($base < ($n/2))

It's not less than it if it's equal.

So, based on all of this, you need to use <=.

You may also want to read over what I said earlier about cutting it off sooner based on $n-$base. And same for $n/$i in isPrime()