Amazon.com Widgets Fun Code of the Week #6: Primality Checking

Fun Code of the Week #6: Primality Checking

By Nick at October 27, 2012 09:02
Filed Under: Delphi, Fun Code

 

I decided to give KhanAcademy a spin, and watched this set of videos:

Level 1: Primality Test

And that let to me writing this code:

function IsPrime(const x: integer): Boolean;
var
  i: integer;
begin
  i := 2;
  repeat
    if X mod i = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(i);
  until i > Sqrt(x);
  Result := True;
end;

I know that this can be optimized (which I'll do if I end up watching the next video :-) ), but I don't often write really geeky code like this, so I thought I'd post it so you all can write lots of comments like you always do when I post code. ;-)

UPDATE #1: There was a bug if you passed in a negative number. 

function IsPrime(const x: integer): Boolean;
var
  i: integer;
begin
  if (x <= 2) then
  begin
    Result := False;
    Exit;
  end;
  i := 3;
  repeat
    if X mod i = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(i);
  until i > Sqrt(x);
  Result := True;
end;

UPDATE #2:  Took the Sqrt() call out of the loop.

function IsPrime(const x: integer): Boolean;
var
  i: integer;
  Wall: double;
begin
  if (x <= 2) then
  begin
    Result := False;
    Exit;
  end;
  i := 3;
  Wall := Sqrt(x);
  repeat
    if X mod i = 0 then
    begin
      Result := False;
      Exit;
    end;
    Inc(i);
  until i > Wall;
  Result := True;
end;

UPDATE #3:   The learning and optimizing continues!  I updated the code based on more suggestions, but the special case of 2 is irritating me.  I confess I thought a while (I’m not cheating by looking up implementations on Google…) and so I came up with something of a hack.  Also, just for Julian, all the x’s are lowercase now.  Smile with tongue out  Also, I learned/re-learned that 1 is not a prime either, by definition.  Interesting.  Any more optimizations out there?  Is there a “correct” way to handle 2?  The end goal here is to have a really nice, really efficient IsPrime function. 

function IsPrime(const x: integer): Boolean;
var
  i: integer;
  Wall: integer;
begin
  if x = 2 then
  begin
    Result := True;
    Exit;
  end;
  i := 3;
  Result := not ((x < i) or (x mod 2 = 0));
  if not Result then Exit;
  Wall := Trunc(Sqrt(x));
  repeat
    Result := not (X mod i = 0);
    if not Result then Exit;
    Inc(i, 2);
  until i > Wall;
  Result := True;
end;
blog comments powered by Disqus

My Book

A Pithy Quote for You

"If you don't buy the tool you need, you will eventually pay for it, but not have your tool."    –  Henry Ford

Amazon Gift Cards

General Disclaimer

The views I express here are entirely my own and not necessarily those of any other rational person or organization.  However, I strongly recommend that you agree with pretty much everything I say because, well, I'm right.  Most of the time. Except when I'm not, in which case, you shouldn't agree with me.