By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,425 Members | 2,549 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,425 IT Pros & Developers. It's quick & easy.

Sieve of Eratosthenes

P: n/a
hi there!

i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.

and here it is:

1 <?php
2 $m = $_POST['max'];
3
4 for ($i=2; $i<=$m; $i=$i+1)
5 {$prime='true';
6 for ($n=2; $n<=sqrt($m); n=n+1)
7 {
8 if (i/n=0)
9 {$prime='false';}
10 if ($prime='true')
11 {echo $i;}
12 }
13 }
14
15 ?>

i constantly get the following error:

Parse error: parse error, unexpected '=', expecting ')' in
C:\Programme\winampp\xampp\htdocs\primzahl.php on line 6

but i cannot find a mistake in line 6. can you? i hope so. but maybe
the mistake lies somewhere else too. i don't know.

i hope someone can help. thanx.
Jul 17 '05 #1
Share this Question
Share on Google+
20 Replies


P: n/a
I noticed that Message-ID:
<c1**************************@posting.google.com > from MSiegel contained
the following:
i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.


But the sieve of Eratosthenes doesn't work the way you coded it. Your
assignment was probably intended to get you working with arrays. A
quick google found the following pseudocode

PSEUDOPROGRAM:

Set up an array of integers z[N]:
for i from 0 to N, set z[i] = i.

for i from 2 to N, mark all multiples
of i by setting them to zero
(or in php, you could unset the value in the array)

for i from 2 to N,
print all unmarked multiples.

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/
Jul 17 '05 #2

P: n/a
Since this is homework, no one will just give you the answer, but
here's a few clues:

Line 6: Look at the way you are declaring the variable 'n'

Line 10: Something is wrong with your comparison statement
'if($prime='true')'

Jul 17 '05 #3

P: n/a
I noticed that Message-ID: <gd********************************@4ax.com>
from Geoff Berrow contained the following:
i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.


But the sieve of Eratosthenes doesn't work the way you coded it.

http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm
--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/
Jul 17 '05 #4

P: n/a
On Wed, 29 Dec 2004 06:43:58 -0800, MSiegel wrote:
Path:
nwrddc03.gnilink.net!cyclone2.gnilink.net!cyclone1 .gnilink.net!gnilink.net!
news.glorb.com!postnews.google.com!not-for-mail
From: ms*****@gmx.de (MSiegel)
Newsgroups: comp.lang.php
Subject: Sieve of Eratosthenes
Date: 29 Dec 2004 06:43:58 -0800
Organization: http://groups.google.com
Lines: 34
Message-ID: <c1**************************@posting.google.com >
NNTP-Posting-Host: 145.254.77.150
X-Trace: posting.google.com 1104331438 32691 127.0.0.1 (29 Dec 2004 14:43:58
GMT)
X-Complaints-To: gr**********@google.com
NNTP-Posting-Date: Wed, 29 Dec 2004 14:43:58 +0000 (UTC)
Xref: cyclone1.gnilink.net comp.lang.php:74427
X-Received-Date: Wed, 29 Dec 2004 09:43:59 EST (nwrddc03.gnilink.net)
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
hi there!

i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.

and here it is:

1 <?php
2 $m = $_POST['max'];
3
4 for ($i=2; $i<=$m; $i=$i+1)
5 {$prime='true';
6 for ($n=2; $n<=sqrt($m); n=n+1)
7 {
8 if (i/n=0)
9 {$prime='false';}
10 if ($prime='true')
11 {echo $i;}
12 }
13 }
14
15 ?>

i constantly get the following error:

Parse error: parse error, unexpected '=', expecting ')' in
C:\Programme\winampp\xampp\htdocs\primzahl.php on line 6

but i cannot find a mistake in line 6. can you? i hope so. but maybe
the mistake lies somewhere else too. i don't know.

i hope someone can help. thanx.


In other news, line 8 will evaluate "true" only when $i is zero (never).
Maybe you meant some other operator? I'm looking sort of in the direction
of the middle-sized number keys... ;)
Jul 17 '05 #5

P: n/a
MSiegel wrote:
hi there!

i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.

and here it is:

1 <?php
2 $m = $_POST['max'];
3
4 for ($i=2; $i<=$m; $i=$i+1)
5 {$prime='true';
6 for ($n=2; $n<=sqrt($m); n=n+1)
7 {
8 if (i/n=0)
9 {$prime='false';}
10 if ($prime='true')
11 {echo $i;}
12 }
13 }
14
15 ?>

i constantly get the following error:


You are constantly forgetting the $ infront of a variable name, which is
required in PHP, unless it is a constant, and in that case, you can't
assign to it.
You might also want to have a look at the ++ operator.

--
Tommy

Jul 17 '05 #6

P: n/a
"Steve" <sc****@comcast.net> wrote:
Since this is homework, no one will just give you the answer, but
here's a few clues:

Line 6: Look at the way you are declaring the variable 'n'
And by "declaring" he doesn't mean the initial declaration ("$n = 2"), but
the iterative step declaration ("n=n+2").

Line 10: Something is wrong with your comparison statement
'if($prime='true')'


Here's the list of comparison operators:
http://www.php.net/manual/en/languag...comparison.php

-Noah
Jul 17 '05 #7

P: n/a
Tommy Gildseth wrote:
MSiegel wrote:
i have to program the sieve of eratosthenes in php as a homework.
Well, since you're being so honest about it....other people have pointed out
some of the *errors* in the script, but your programming style is abysmal.

Have a read at http://pear.php.net/manual/en/standards.php for starters.

Use readable variable names.
4 for ($i=2; $i<=$m; $i=$i+1)
5 {$prime='true';
6 for ($n=2; $n<=sqrt($m); n=n+1)

$m does not change throughout the life of the program but you are
calculating it's square root $m^1.5 times! It should be calculated once,
outside of both loops.

Once you know it's not prime, why bother to continue the loop?
7 {
8 if (i/n=0)
9 {$prime='false';}
10 if ($prime='true')
11 {echo $i;}
12 }
13 }
14
15 ?>


There are also semantic errors in there too.

HTH

C.

Jul 17 '05 #8

P: n/a
"MSiegel" <ms*****@gmx.de> wrote in message
news:c1**************************@posting.google.c om...
hi there!

i have to program the sieve of eratosthenes in php as a homework.
after i had created an html file where the maximum is set i wrote a
php script which doesn't work properly - actually it doesn't work at
all.

and here it is:

1 <?php
2 $m = $_POST['max'];
3
4 for ($i=2; $i<=$m; $i=$i+1)
5 {$prime='true';
6 for ($n=2; $n<=sqrt($m); n=n+1)
Along with everyone else's comments about your programming, try examining
this little program:

<?php

$m = 100;

for($i = 2; $i < 100; $i++)
{
echo "$i) " . sqrt($m) . "<br>\n";
}

?>

You'll notice that the square root of $m does not change during the
execution of the program, so calculating it every time you do a loop is:

a) unessecary
b) time consuming
7 {
8 if (i/n=0)
The sieve of of eratosthenes is a question about multiplication and
elimination, not division. If you have to divide something then you're doing
it wrong.
9 {$prime='false';}
10 if ($prime='true')
11 {echo $i;}
12 }
13 }
14
15 ?>

i constantly get the following error:

Parse error: parse error, unexpected '=', expecting ')' in
C:\Programme\winampp\xampp\htdocs\primzahl.php on line 6

but i cannot find a mistake in line 6. can you? i hope so. but maybe
the mistake lies somewhere else too. i don't know.

i hope someone can help. thanx.


Pay particular attention to Geoff Berrow's advice and link.

Jul 17 '05 #9

P: n/a
CJ Llewellyn wrote:
<snip>
The sieve of of eratosthenes is a question about multiplication and
elimination, not division. If you have to divide something then you're doing
it wrong.

<snip>

After looking at the explanation of the algorithm here:

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

I'm wondering, How one goes about determining if a number is a multiple
of another without dividing?

NM
Jul 17 '05 #10

P: n/a
News Me wrote:
I'm wondering, How one goes about determining if a number is a
multiple of another without dividing?


Simple, by using mod (e.g. 6 % 2)
JW

Jul 17 '05 #11

P: n/a
News Me wrote:
How one goes about determining if a number is a multiple
of another without dividing?


With subtractions (a *LOT* of subtractions!)
php$ cat mult.php
<?php
function ismultiple($n, $m) {
/* needs validation: $n and $m should be positive integers */
$a = max($n, $m);
$b = min($n, $m);
while ($a > $b) $a -= $b;
if ($a == $b) return true;
return false;
}

$a = $argv[1];
$b = $argv[2];
echo "$a and $b are";
if (!ismultiple($a, $b)) echo ' *NOT*';
echo " multiples\n";
?>

A sample run:
php$ php mult.php 17 1700
17 and 1700 are multiples

And another run, this time with larger values ('time' is the bash
builtin variant)
php$ time php mult.php 17 17000001
17 and 17000001 are *NOT* multiples

real 0m3.453s
user 0m3.430s
sys 0m0.010s
Yes! My computer is a slow 500MHz PC :(

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!
Jul 17 '05 #12

P: n/a
"News Me" <newsTWOme@pacifierDOTcom> wrote in message
news:10*************@corp.supernews.com...
CJ Llewellyn wrote:
<snip>
The sieve of of eratosthenes is a question about multiplication and
elimination, not division. If you have to divide something then you're doing it wrong.

<snip>

After looking at the explanation of the algorithm here:

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

I'm wondering, How one goes about determining if a number is a multiple
of another without dividing?


By finding all the multiples and removing them from your list ;)

2 x 2 = 4

2 x 3 = 6

2 x 4 = 8

2 x 5 = 10

....

3 x 2 = 6

3 x 3 = 9

3 x 4 = 12

3 x 5 = 15

....

Now would you need to do the 4 x ?

You've already calculated that 4 is a product of 2 x 2, the same applies to
6 , 8 , 9 , 12 ..

However 5, 7, 11 haven't shown up on your list, so you need to multiple
those numbers out.
Jul 17 '05 #13

P: n/a
Pedro Graca wrote:
News Me wrote:
How one goes about determining if a number is a multiple
of another without dividing?


With subtractions (a *LOT* of subtractions!)


Why not use modulo as I suggested before? Ok, it's still division, but a lot
faster.

Time this function:

function ismultiple($n, $m) {
$a = max($n, $m);
$b = min($n, $m);
return !($a % $b);
}
JW

Jul 17 '05 #14

P: n/a
"Janwillem Borleffs" <jw@jwscripts.com> wrote in message
news:41***********************@news.euronet.nl...
Pedro Graca wrote:
News Me wrote:
How one goes about determining if a number is a multiple
of another without dividing?
With subtractions (a *LOT* of subtractions!)


Why not use modulo as I suggested before? Ok, it's still division, but a

lot faster.


Because the problem is about avoiding division.
Jul 17 '05 #15

P: n/a
Janwillem Borleffs wrote:
Pedro Graca wrote:
News Me wrote:
How one goes about determining if a number is a multiple
of another without dividing?
^^^^^^^^^^^^^^^^
With subtractions (a *LOT* of subtractions!)
Why not use modulo as I suggested before?
Ok, it's still division, but a lot faster.

^^^^^^^^^^^^^^^^^^^

Well ... that's the reason why not use modulo :-)

Had the question been "How to determine if a number is a multiple of
another?", the modulo approach would be the best bet.
Time this function:

function ismultiple($n, $m) {
$a = max($n, $m);
$b = min($n, $m);
return !($a % $b);
}


No need to time it. It executes instantaneously.

Maybe the OP is building his own simple processor that cannot do
divisions.
He'll have a very hard time compiling PHP for it though :-)

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!
Jul 17 '05 #16

P: n/a
CJ Llewellyn wrote:
"News Me" <newsTWOme@pacifierDOTcom> wrote in message
news:10*************@corp.supernews.com...
CJ Llewellyn wrote:
<snip>
The sieve of of eratosthenes is a question about multiplication and
elimination, not division. If you have to divide something then you're
doing
it wrong.


<snip>

After looking at the explanation of the algorithm here:

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

I'm wondering, How one goes about determining if a number is a multiple
of another without dividing?

By finding all the multiples and removing them from your list ;)

2 x 2 = 4

2 x 3 = 6

2 x 4 = 8

2 x 5 = 10

...

3 x 2 = 6

3 x 3 = 9

3 x 4 = 12

3 x 5 = 15

...

Now would you need to do the 4 x ?

You've already calculated that 4 is a product of 2 x 2, the same applies to
6 , 8 , 9 , 12 ..

However 5, 7, 11 haven't shown up on your list, so you need to multiple
those numbers out.


OK, great! Is 7 a multiple of 62298863484143?

NM
Jul 17 '05 #17

P: n/a
News Me wrote:
OK, great! Is 7 a multiple of 62298863484143?


No
--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
Jul 17 '05 #18

P: n/a
John Bokma wrote:
News Me wrote:

OK, great! Is 7 a multiple of 62298863484143?

No


You were supposed to show your math. Without dividing (or modulating).

NM
Jul 17 '05 #19

P: n/a
"News Me" <newsTWOme@pacifierDOTcom> wrote in message
news:10*************@corp.supernews.com...
John Bokma wrote:
News Me wrote:

OK, great! Is 7 a multiple of 62298863484143?

No


You were supposed to show your math. Without dividing (or modulating).


if(7 < 62298863484143)
echo "No it's not";

Jul 17 '05 #20

P: n/a
News Me wrote:
John Bokma wrote:
News Me wrote:
OK, great! Is 7 a multiple of 62298863484143?
No
You were supposed to show your math. Without dividing (or modulating).


No need for great maths here. 7 is not a multiple of 14 :-)

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!
Jul 17 '05 #21

This discussion thread is closed

Replies have been disabled for this discussion.