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. 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;```