I decided to give KhanAcademy a spin, and watched this set of videos:
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;