prime numbers up to a certain number

[Jahongir]

Dear developers,

 

I was solving problems to improve my algorithmic abilities. So, here is one of them:

I need to "echo" all the prime numbers to the browser up to  certain number.

So, if the number is 8, for example, I need to echo 2,3,5 and 7.

 

here is my code:

 

$a = 100;

 

for($i = 2; $i<=$a; $i++)

{

    if($i == 2)

    {

        echo "2</br>";

    }

 

 

    for($j =3; $j <= ceil($i/2); $j = $j + 2)

    {

        if($i % 2 == 0)

        {

            break;

        }

        if ($i % $j == 0)

        {

            break;

        }

        else

        {

            continue;

        }

    }

}

 

not working properly!

 

Please Help !!!

[Barand]

Have you tried implementing the "Sieve of Eratosthenes"

[Jahongir]

Do you mean this? :

$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? Thanks for help

[Barand]

I had something like this in mind

$n = 56;
$numbers = array_fill_keys(range(2,$n),1);
$lim = ceil(sqrt($n));
for ($i=2; $i<$lim; $i++) {
    $k=2;
    while ($i*$k <= $n) {
        $numbers[$i*$k++] = 0;   
    }
}
echo join(', ', array_keys(array_filter($numbers)));

//--> 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53

[Jahongir]

Thank you Barand)

it is impressive

but...

too difficult for me 

Thanx anyway)

[Barand]

The principle is quite simple

 

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes