> From: Stuart White [mailto:[EMAIL PROTECTED]
> Sent: Tuesday, 2 March 2004 11:55 PM
> To: David le Blanc; [EMAIL PROTECTED]
> Subject: RE: listing prime numbers in a range (Beginning Perl
> exercise)
>
>
> --- David le Blanc
> <[EMAIL PROTECTED]> wrote:
> >
> > Just for the sake of it, and I apologise profusely
> > for the top posting..
> >
> stuart>Hi David,
>
>
> > Here is a summary of the posted prime calculators
> > for testing your
> > results against.
> >
> > >(1) Ohad
>
> stuart>I saw his regexp soln. I was attempting to
> stuart>solve it with arrays, loops and maybe hashes.
> stuart>I figure that the exercise wouldn't be in the
> stuart>book before the regexp chapter if I couldn't do
> stuart>it easily (or without TOO much difficulty)
> stuart>without them. That's all.
>
> > >(2) Joseph
> stuart>I thought this one was a joke. Partly because
> stuart>of the context it was sent in, partly because
> stuart>of what I saw it do. I ran it, and it printed
> stuart>out a slew of numbers. It didn't stop after a
> stuart>few minutes, so I ended the program.
You just have to realise that the script is printing the entire
array of primes EVERY time it finds a new one. change the
'while (1)' to 'while( $#primes < 2000 )' to only find 1000
primes, and move the 'print' to after the loop.
>
>
> > >(3) me (Hey, it's a Mee Too!)
> >
> #-------------------------------------------------------
> > $max=shift||17393;
> > %notprime=();
> > @prime=();
> >
> > for $n (2..$max){
> > unless($notprime{$n}){
> > push @prime,$n;
> > $notprime{$_*$n}=1 for 2..$max/$n;
> > }
> > }
> >
> > print "Found $#prime prime numbers..".$/;
> > print "@prime\n";
> >
> #-------------------------------------------------------
> >
> > Brief explanation..
> > (1)
> sounds neat.
>
> > (2) Joseph posted a calculator which uses the
> > feature of prime numbers
> > that the
> > largest number you need to divide it by is the
> > square root of itself
> > ($_**0.5)
> > and that you only need to test if the number you
> > are examining is
> > divisible
> > (ie mod==0) by another prime you have already
> > found. Hence, very
> > quick and
> > very cpu/memory cheap. Why not test against
> > every number? If you
> > test against
> > a non-prime number, you are simply testing
> > against a multiple of a
> > prime of
> > course.
See above. It does work afaik.
>
> stuart>Ahh, this makes sense, sortof. I'm going to
> stuart>need to look at the code again and your
> stuart>explanation. This was printing many, many,
> stuart>many numbers, some of which sure didn't look
> stuart>like they were primes. The sheer number plus
> stuart>the proximity of them to each other in
> stuart>cardinal? order (2341 2347 2443 etc) (these
> stuart>numbers are used to illustrate my probably
> stuart>improper use of cardinal, I'm not implying that
> stuart>those numbers were outputted by the program)
> stuart>made me think that some weren't primes.
>
>
> >
> > (3) A very simple implementation of an erogenous
> > sieve (iud? did I say
> > that wrong?)
> > which keeps all primes in '@primes' and all
> > 'eliminated' entries in
> > '%notprime'.
> > quick, but likely more memory intensive than
> > (2).
>
> This one is a bit confusing.
> $max=shift||17393;
> stuart>I thought shift was to remove an element from
> stuart>the beginning of an array, but it's being used
> stuart>in scalar context here. Why? And what is it
> stuart>doing?
When 'shift' has no argument, it shifts '@_' which is parameter
arguments in a function, and command line arguments elsewhere.
$max = shift will grab the first command line argument. If
there isn't one, shift == undef, so perl will complete the 'x||y'
expression by evaluating 'y'. If 'shift' returns a number, the 'x||y'
expression is shortcut.
Hence, $max = first argument OR 17393 if there isn't one.
>
> %notprime=();
> > @prime=();
> >
> > for $n (2..$max){
> stuart>this makes me think that you were somehow
> stuart>assigning a number to $max above. But where
> stuart>does 17393 come in? Why not 17394, or 18000?
17393 is a completely magic number it just so happens where are
exactly 2000 prime numbers between 2 and 17393 inclusive.
>
>
> > unless($notprime{$n}){
> > push @prime,$n;
> > $notprime{$_*$n}=1 for 2..$max/$n;
> stuart>I'm not sure I understand this line directly
> stuart>above. What I think it says is that it is
> stuart>accessing the value within the %notprime hash
> stuart>where the key equals the last inputted number
> stuart>which I suppose is $n and $_ if $n was pushed
> stuart>onto @prime, but just $_ if $n was not pushed
> stuart>onto @prime. I don't get the "=1" part
> stuart>though. What is that doing? I'm assuming that
> stuart>is a for loop there that is working like a
> stuart>foreach loop? but I'm not quite sure what it's
> stuart>doing.
>
How about:
for($i= $n*2; $i<$max; $i = $i+$n) {
$notprime{$i} = 1
}
In order to set an entry in the 'notprime' hash for every
multple of '$n' from $n*2 to $max, I iterate from 2 to $max/$n
and set '$notprime{ <current iteration>*$n } = true'.
Hence, when $n is 2,
$notprime{ 2*2 } = 1;
$notprime{ 2*3 } = 1;
$notprime{ 2*4 } = 1;
$notprime{ 2*5 } = 1;
$notprime{ 2*6 } = 1;
... until $notprime{ 2*($max / 2) } = 1
> > Cheers.
> > David
> >
> >
>
> __________________________________
> Do you Yahoo!?
> Yahoo! Search - Find what you're looking for faster
> http://search.yahoo.com
>
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>
