From: Josh Cheek <josh.cheek@...>
Date: 2012-04-15T03:09:38+09:00
Subject: Re: Arguments with Funktion

--f46d04428400df55f604bda77dcc
Content-Type: text/plain; charset=ISO-8859-1

On Fri, Apr 13, 2012 at 8:09 AM, Peter Hickman <
peterhickman386@googlemail.com> wrote:

>
> Actually there are better ways to check for prime numbers between a
> and b (hint: 2 is the only *even* prime, why are you even looking at
> any others?)
>
>
In the same way you can rule out all all multiples of 2, you can rule out
all multiples of 3 and 5 and 7 and so on. This means you only need to see
if your number is divisible by any primes (if it is divisible by 4 or 6 or
8, then it is also divisible by 2).

So we can write it like this:

def prime(upper_limit)
  return [] if upper_limit < 2
  (3..upper_limit).each_with_object [2] do |potential_prime, primes|
    next if primes.any? { |prime| potential_prime % prime == 0 }
    primes << potential_prime
  end
end



prime 1   # => []
prime 2   # => [2]
prime 3   # => [2, 3]
prime 4   # => [2, 3]
prime 5   # => [2, 3, 5]
prime 6   # => [2, 3, 5]
prime 7   # => [2, 3, 5, 7]
prime 8   # => [2, 3, 5, 7]
prime 9   # => [2, 3, 5, 7]
prime 10  # => [2, 3, 5, 7]
prime 11  # => [2, 3, 5, 7, 11]
prime 12  # => [2, 3, 5, 7, 11]
prime 13  # => [2, 3, 5, 7, 11, 13]
prime 14  # => [2, 3, 5, 7, 11, 13]
prime 15  # => [2, 3, 5, 7, 11, 13]
prime 16  # => [2, 3, 5, 7, 11, 13]
prime 17  # => [2, 3, 5, 7, 11, 13, 17]
prime 18  # => [2, 3, 5, 7, 11, 13, 17]
prime 19  # => [2, 3, 5, 7, 11, 13, 17, 19]
prime 20  # => [2, 3, 5, 7, 11, 13, 17, 19]



If we wanted to get elaborate, we could introduce a cutoff at the square
root:

def prime(upper_limit)
  return [] if upper_limit < 2
  (3..upper_limit).each_with_object [2] do |potential_prime, primes|
    cutoff = Math.sqrt potential_prime
    next if primes.take_while { |prime| prime <= cutoff }.any? { |prime|
potential_prime % prime == 0 }
    primes << potential_prime
  end
end


If you needed this to be super fast, there would be better ways to write
this (as in faster, but harder to understand and read), but this shows the
basic idea.

--f46d04428400df55f604bda77dcc
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Fri, Apr 13, 2012 at 8:09 AM, Peter Hickman <span dir=3D"ltr">&lt;<a hre=
f=3D"mailto:peterhickman386@googlemail.com">peterhickman386@googlemail.com<=
/a>&gt;</span> wrote:<br><div class=3D"gmail_quote"><blockquote class=3D"gm=
ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex">
<br>
Actually there are better ways to check for prime numbers between a<br>
and b (hint: 2 is the only *even* prime, why are you even looking at<br>
any others?)<br>
<br>
</blockquote></div><br><div>In the same way you can rule out all all multip=
les of 2, you can rule out all multiples of 3 and 5 and 7 and so on. This m=
eans you only need to see if your number is divisible by any primes (if it =
is divisible by 4 or 6 or 8, then it is also divisible by 2).</div>
<div><br></div><div>So we can write it like this:</div><div><div><div><br><=
/div><div><div>def prime(upper_limit)</div><div>=A0 return [] if upper_limi=
t &lt; 2</div><div>=A0 (3..upper_limit).each_with_object [2] do |potential_=
prime, primes|</div>
<div>=A0 =A0 next if primes.any? { |prime| potential_prime % prime =3D=3D 0=
 }</div><div>=A0 =A0 primes &lt;&lt; potential_prime</div><div>=A0 end</div=
><div>end</div></div><div><br></div><div><br></div><div><br></div><div>prim=
e 1 =A0 # =3D&gt; []</div>
<div>prime 2 =A0 # =3D&gt; [2]</div><div>prime 3 =A0 # =3D&gt; [2, 3]</div>=
<div>prime 4 =A0 # =3D&gt; [2, 3]</div><div>prime 5 =A0 # =3D&gt; [2, 3, 5]=
</div><div>prime 6 =A0 # =3D&gt; [2, 3, 5]</div><div>prime 7 =A0 # =3D&gt; =
[2, 3, 5, 7]</div><div>
prime 8 =A0 # =3D&gt; [2, 3, 5, 7]</div><div>prime 9 =A0 # =3D&gt; [2, 3, 5=
, 7]</div><div>prime 10 =A0# =3D&gt; [2, 3, 5, 7]</div><div>prime 11 =A0# =
=3D&gt; [2, 3, 5, 7, 11]</div><div>prime 12 =A0# =3D&gt; [2, 3, 5, 7, 11]</=
div><div>prime 13 =A0# =3D&gt; [2, 3, 5, 7, 11, 13]</div>
<div>prime 14 =A0# =3D&gt; [2, 3, 5, 7, 11, 13]</div><div>prime 15 =A0# =3D=
&gt; [2, 3, 5, 7, 11, 13]</div><div>prime 16 =A0# =3D&gt; [2, 3, 5, 7, 11, =
13]</div><div>prime 17 =A0# =3D&gt; [2, 3, 5, 7, 11, 13, 17]</div><div>prim=
e 18 =A0# =3D&gt; [2, 3, 5, 7, 11, 13, 17]</div>
<div>prime 19 =A0# =3D&gt; [2, 3, 5, 7, 11, 13, 17, 19]</div><div>prime 20 =
=A0# =3D&gt; [2, 3, 5, 7, 11, 13, 17, 19]</div></div></div><div><br></div><=
div><br></div><div><br></div><div>If we wanted to get elaborate, we could i=
ntroduce a cutoff at the square root:</div>
<div><div><br></div><div>def prime(upper_limit)</div><div>=A0 return [] if =
upper_limit &lt; 2</div><div>=A0 (3..upper_limit).each_with_object [2] do |=
potential_prime, primes|</div><div>=A0 =A0 cutoff =3D Math.sqrt potential_p=
rime</div>
<div>=A0 =A0 next if primes.take_while { |prime| prime &lt;=3D cutoff }.any=
? { |prime| potential_prime % prime =3D=3D 0 }</div><div>=A0 =A0 primes &lt=
;&lt; potential_prime</div><div>=A0 end</div><div>end</div></div><div><br><=
/div><div><br>
</div><div>If you needed this to be super fast, there would be better ways =
to write this=A0(as in faster, but harder to understand and read), but this=
 shows the basic idea.</div>

--f46d04428400df55f604bda77dcc--