RE: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36044] RE: [mg36023] RE: [mg35992] Notebook for Primes
- From: "DrBob" <majort at cox-internet.com>
- Date: Wed, 14 Aug 2002 05:35:12 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
What makes you think log(n)^(log log(n)) isn't dominated by a
polynomial? Actually, it is, and the Sieve of Eratosthenes is
polynomial just like I said. For instance, n^k dominates, for ANY k>0
(including 1):
f[n_] := Log[n]^Log[Log[n]]
Plot[{f[n]/Sqrt[n]}, {n, 1, 100000}]
logF[n_] := Log[Log[n]]^2
Limit[logF[n]/Log[n], n -> Infinity]
In my initial testing, the Sieve is far faster than the new algorithm,
too. FAR faster.
Bobby
-----Original Message-----
From: dterr at wolfram.com [mailto:dterr at wolfram.com]
To: mathgroup at smc.vnet.net
Subject: [mg36044] Re: [mg36023] RE: [mg35992] Notebook for Primes
DrBob wrote:
> The oldest algorithm for testing primes... the Sieve of
Eratosthenes...
> is polynomial and deterministic. It's simply too slow to use, just
like
> the one at the attachment.
>
> Bobby
Actually that's not true. The Sieve of Eratosthenes has complexity
log(n)^(log log(n)). The algorithm below is the first deterministic
primality test known to be polynomial. Unfortunately, it still appears
to
be not practical.
David
> -----Original Message-----
> From: Jeff Dillon [mailto:jeffdi at fidalgo.net]
To: mathgroup at smc.vnet.net
> Subject: [mg36044] [mg36023] [mg35992] Notebook for Primes
>
> Is there a publicly available Mathematica 3.0 notebook that implements
> the Primes is in P?
>
> http://www.msnbc.com/news/792126.asp