Prime Numbers Up to a certain number

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
JohnyStark
Forum Newbie
Posts: 1
Joined: Mon Feb 17, 2014 8:05 am

Prime Numbers Up to a certain number

Post by JohnyStark »

hey guys,

here is the problem, i need to find prime numbers up to a certain number and here is my code:

$a = 56;

for($i = 2; $i<=$a; $i++)
{
if($i == 2)
{
echo "2</br>";
}

if($i == 3)
{
echo "3</br>";
}

if($i == 5)
{
echo "5</br>";
}

if($i == 7)
{
echo "7</br>";
}

for($j =3; $j <= ceil($i/2); $j = $j + 2)
{
if($i % 2 == 0)
{
break;
}
if($i % 3 == 0)
{
break;
}
if($i % 5 == 0)
{
break;
}
if($i % 7 == 0)
{
break;
}
else
{
echo "$i</br>";
break;
}
}
}

It works fine, but it kinda seems like a brute force algorithm, doesnt it? Is there any other way to do this?
Thanks for help!!!
User avatar
Celauran
Moderator
Posts: 6427
Joined: Tue Nov 09, 2010 2:39 pm
Location: Montreal, Canada

Re: Prime Numbers Up to a certain number

Post by Celauran »

Maybe something like this?

Code: Select all

function isPrime($num) {
	$num = abs($num);

	if ($num == 1) {
		return false;
	}

	if ($num == 2) {
		return true;
	}

	if ($num % 2 == 0) {
		return false;
	}

	for ($i = 3, $j = ceil(sqrt($num)); $i <= $j; $i += 2) {
		if ($num % $i == 0) {
			return false;
		}
	}

	return true;
}
Post Reply