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

"We make men without chests and expect of them virtue and enterprise. We laugh at honor and are shocked to find traitors in our midst. We castrate and then bid the geldings to be fruitful."    –  C. S. Lewis

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.