From: Roland Schmitt <Roland.Schmitt@...>
Date: 2005-06-22T17:51:05+09:00
Subject: Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

irb(main):001:0> require "openssl"
=> true
irb(main):002:0> include OpenSSL
=> Object
irb(main):003:0> a=BN.new("103")
=> 103
irb(main):004:0> a.prime?(10)
=> true
irb(main):005:0> a.prime?(nil)
=> true
irb(main):006:0>


It implements the Miller-Rabin-Test.

See http://www.hmug.org/man/3/BN_is_prime.php




Dee Zsombor schrieb:
> How about using a better algorithm than  Eratosthenes sieve invented
> thousands of years ago. In late 2003 a new method was published that
> computes the first n primes using binary quadratic forms. This will
> give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).
> 
> For theoretical description see:
> http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf
> 
> And for a sample implementation in C
> http://cr.yp.to/primegen.html
> 
> cheers,
> zsombor
> --
> http://deezsombor.blogspot.com
> 
> 
>