January 3, 2008
Handbook Note 71/113: Is Prime Number Function
Note 71 (a rather useless one): The IsPrime function is a slow function used to check whether a number is a prime number. I used this function in past editions of Mastering Delphi (up to version 7) because I needed a slow CPU-intensive operation. I know it could be written to perform the same task much faster, but in this case I simply don't need speed, quite the opposite.
Although this is quite useless information outside of the scope of the book, do you know where I can find a very optimized version of a function to check for prime numbers? Could be an interesting comparison...
This blog post is part of my "113 Delphi 2007 Handbook Notes" blogging project, to promote my new Delphi book.
4 Comments
Handbook Note 71/113 Is Prime Number Function
Yes, much simple way - not a deterministic, the
probability function; see the "Rabin-Miller" test for
more details.
the "Lehmann" sample:
<pre>
// tested on D7
program test_lehmann;
{$APPTYPE CONSOLE}
uses
SysUtils;
// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
a,z,r,q: int64;
begin
p := abs(p);
// test for small numbers
if p<4 then
begin
result := true;
exit;
end;
// get the random a for the probe
repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
z := a;
r := (p-1) div 2;
q := 1;
while r>0 do
begin
z := (z*z) mod p;
if (r and 1) = 1 then q := (q * z) mod p;
r := r shr 1;
end;
// the result
result := (q = 1) or (q = (p-1));
end;
// numbers must be big!
function prime_lehmann(p,n: Integer): Boolean;
var
m: Integer;
begin
if n<0 then
begin
result := false;
exit;
end;
// this is only for this demo
write('is the ',p,' prime? - ');
m := n;
result := true;
while (result) and (n>0) do
begin
result := lehmann_probe(p);
dec(n);
end;
// this is only for this demo
writeln(result,', number of probes ',m-n);
end;
var
i,j: Integer;
begin
randomize;
j := 100+random(1000000);
for i := j to (j+100) do prime_lehmann(i,30);
readln;
end.
</pre>
Comment by Leonid Koninin on January 3, 18:12
Handbook Note 71/113 Is Prime Number Function
sorry, mistype in previous source, must be:
// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
a,z,r,q: int64;
begin
p := abs(p);
// test for small numbers
if p<4 then
begin
result := true;
exit;
end;
// get the random a for the probe
repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
z := a;
r := (p-1) div 2;
q := 1;
while r>0 do
begin
if (r and 1) = 1 then q := (q * z) mod p;
z := (z*z) mod p;
r := r shr 1;
end;
// the result
result := (q = 1) or (q = (p-1));
end;
Comment by Leonid Koninin on January 3, 18:24
Handbook Note 71/113 Is Prime Number Function
When you think of core Delphi functions and Fast, you should think of FastCode ;-) http://fastcode.sourceforge.net/challenge_content/IsPrime.html Seems to be an old BV style because the RTL function is not included (Which nowadays is) So I can't give the correct speedup above RTL, but I assume it's goood :)Comment by Davy Landman [http://delphi-snippetrs.blogspot.com] on January 7, 17:18
Post Your Comment
Click here for posting your feedback to this blog.
There are currently 0 pending (unapproved) messages.
Handbook Note 71/113 Is Prime Number Function
Comment by Luigi D. Sandon on January 3, 10:54