Mayur, even though primality testing has been proven to be polynomial in time, the randomized ones are what are being used due to efficiency considerations.
Arul, you may be better off searching for Rabin-Miller test. Wikipedia also has an interesting article with further links.
Cheers,
Nat
On 4/29/06, Mayur <[EMAIL PROTECTED]> wrote:
Hi,
If you are looking for primality testing, google for the paper "Prime is in P". The original paper's by three IIT-Kanpur people. The papers that followed up give the best algorithms for checking primality.
If you are looking for prime number generation, look out for "sieve methods" - especiialy generalized sieves.On 4/29/06, B. P. TBC < [EMAIL PROTECTED]> wrote:
This algorithm (in Pascal) returns True, if x is a prime number, and
returns False, if x isn't prime.
function Prime(x: word): boolean;
var i: word;
v: boolean;
Begin
v := False;
if x=1 then v := True;
for i:=2 to round(sqrt(x)) do Begin
if x mod i = 0 then v := True;
End;
Prime := not v;
End;
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
