Looking for files of prime numbers
Gottfried Barthel
can anyone of you point out to me where to find lists of consecutive
primes say up to the range of the 50000th prime on the web? Reason: For
experimentally checking which prime numbers have some specific property,
I am running Maple's built-in "ithprime" function for increasingly
larger values of the counter. Maple's "ithprime" reads the first N
primes off from a list (where N is slightly larger than 30000), but as
soon as one wants to exceed these bounds, things get really very much
slowed down: Whereas the kind of test I want to do takes some 50 seconds
for the 500 primes in the range 24500 .. 25000, it takes some 10 minutes
for the 125 primes in the range 37000 .. 37125, most of which is
certainly used for finding these primes.
Any help would be appreciated.
Regards from Konstanz,
Gottfried Barthel
Fachbereich Mathematik und Statistik, Universitaet Konstanz
--
Mit freundlichen Gruessen
Gottfried Barthel
----------------------------------------------------------------------
___
/ \ Gottfried Barthel | Tel: [++49/0] 7531 88 27 93
| _____ Fachbereich Mathematik | Fax: [++49/0] 7531 88 30 36
| | \ und Statistik | e-mail:
\___|___/ Universitaet Konstanz | Gottfrie...@uni-konstanz.de
| \ Fach D 203 | WWW:
_|___/ D-78457 Konstanz | www.mathe.uni-konstanz.de/
| ~barthel/
----------------------------------------------------------------------
(Fixed-width font, line lenght at least 72 characters)
fredm
"Gottfried Barthel" <Gottfrie...@fmi.uni-konstanz.de> wrote in message
news:3B67D5D8...@fmi.uni-konstanz.de...
Raymond Manzoni
Hello,
One possibility should be to use the free pari/gp
http://www.gn-50uma.de/ftp/pari/00index.html
which is very powerful for number theory.
It allows to use up to 436273009 precomputed values (try for example
primelimit = 420M in .gprc file) and has special functions to parse
prime numbers (forprime() uses the table and is quick) and so on.
To see you numbers type something like :
> forprime(p=1,420*10^6,print(p))
Good luck,
Raymond
Raymond Manzoni
Hello,
One possibility should be to use the free pari/gp
http://www.gn-50uma.de/ftp/pari/00index.html
which is very powerful for number theory.
It allows to use prestored primes up to 436273009 (try for example
primelimit = 420M in .gprc file) and has special functions to parse
prime numbers (forprime(), prime() use the table and are quick) and so
on.
To generate you table type something like :
> forprime(p=1,420*10^6,print(p))
Good luck,
Raymond
Nico Benschop
>
> Dear Newgroup readers,
> can anyone of you point out to me where to find lists of consecutive
> -- Gottfried Barthel
Try "The Prime pages" of prof. Chris Caldwell,
for just about _anything_ regarding primes:
http://www.utm.edu/~caldwell/ -- NB
Richard B. Kreckel
: can anyone of you point out to me where to find lists of consecutive
: primes say up to the range of the 50000th prime on the web? Reason: For
: experimentally checking which prime numbers have some specific property,
: I am running Maple's built-in "ithprime" function for increasingly
: larger values of the counter. Maple's "ithprime" reads the first N
: primes off from a list (where N is slightly larger than 30000), but as
: soon as one wants to exceed these bounds, things get really very much
: slowed down: Whereas the kind of test I want to do takes some 50 seconds
: for the 500 primes in the range 24500 .. 25000, it takes some 10 minutes
: for the 125 primes in the range 37000 .. 37125, most of which is
: certainly used for finding these primes.
:
: Any help would be appreciated.
Why not hack a sieve in a few lines of C-code?
: Regards from Konstanz,
Regards from downstream
-richy.
--
Richard B. Kreckel
<Richard...@GiNaC.DE>
<http://www.ginac.de/~kreckel/>
Gottfried Barthel
great!
A surprisingly simple and efficient Maple solution has been communicated
to me directly by David G Radcliffe:
primes := array(1..50000):
p := 1:
for i from 1 to 50000 do
p := nextprime(p):
primes[i] := p
od:
This works really well; on the SUN Ultra 10 (300 MHz) in my office, it
takes less than two minutes. The next 50000 primes take significantly
more time -- about 8 1/2 minutes --, but this is still quite reasonable.
This shows that Maple's "nextprime" is much more efficient than
"ithprime" in finding prime numbers, which comes as kind of surprise.
Gottfried Barthel
this is a brief addendum to the previous message:
I just checked that at the beginning, a simple additional "if"-switch in
the code allows to speed up things considerably by using Maple's
built-in "ithprime" up to i=30000, say, instead of "nextprime":
primes := array(1..50000):
for i from 1 to 50000 do
if p <= 30000 then
p := ithprime(i)
else
p := nextprime(p):
fi;
primes[i] := p
od:
It thus took Maple 8 sec. instead of 53 sec. on my own Mac G3 PowerBook
with a 233 Hz CPU to go through the range up to 30000, since the values
are just read off the table. If the range does not exceed 50000 too
much, this may be worth while; for a significantly larger range,
however, these 45 sec. do not matter too much any more ...
KBH
primes between a (trillion - 500) and a (trillion) in about 13 seconds on a
200 mhz computer. However, on a second run it uses an array in memory and
will run in about 3 seconds. So after a set-up maximum run, it will
calculate any block of 500 primes, less than a U.S. trillion, almost
instantly.
Dann Corbit
news:SLX97.66$HL7.7...@newssvr15.news.prodigy.com...
How long will it take to calculate one trillion primes in total?
What algorithm are you using?
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
KBH
(trillion), it is calculating all the primes up to the square root of a
trillion and putting them into a factorization array.
So (on a 200 mhz computer) it takes about 13 seconds to make the maximum
array and calculate the maximum block. Once that is done then it only takes
about 3 seconds to calculate the maximum block on a repeat run. So it takes
the program about 10 seconds to
calculate ALL the primes up to the square root of a U.S. trillion.
The program is a KBH optimization of the fact that an odd number is prime if
it is divided by all the primes up to its square root without finding a zero
remainder. Oh, that is 'PrimeRun v3.0' that keeps track of the factorization
array in RAM memory.
The reason that I have not uploaded the program to my web server is just
that an "About" window and a "License Product" window has not yet been
added. Well, primes up to a trillion are small primes and so the program has
been a developer's utility.
Robert Israel
Gottfried Barthel <Gottfrie...@uni-konstanz.de> wrote:
>A surprisingly simple and efficient Maple solution has been communicated
>to me directly by David G Radcliffe:
> primes := array(1..50000):
> p := 1:
> for i from 1 to 50000 do
> p := nextprime(p):
> primes[i] := p
> od:
>This works really well; on the SUN Ultra 10 (300 MHz) in my office, it
>takes less than two minutes. The next 50000 primes take significantly
>more time -- about 8 1/2 minutes --, but this is still quite reasonable.
>This shows that Maple's "nextprime" is much more efficient than
>"ithprime" in finding prime numbers, which comes as kind of surprise.
I don't know how you come to that conclusion.
On my computer (Pentium II/266, Windows 95) in Maple 7, Radcliffe's
program took 62 seconds, but the following took less than 41 seconds:
primes:= array(1..50000);
for i from 1 to 50000 do
primes[i] := ithprime(i)
od:
Both ithprime(i) (if i < 100000) and nextprime(p) use very similar
strategies: they search for primes among odd numbers, starting at
p+1 or p+2 in the case of nextprime or at ithprime(i-1)+2 in the
case of ithprime. The one difference is that ithprime checks
that the gcd of the candidate and 3929160775540133527939545
(which is the product of primes from 3 to 67) is 1 before calling
isprime, while nextprime calls isprime directly. If ithprime(i-1)
is known (as it is in this loop), ithprime is very efficient.
Of course if you call ithprime(i) when ithprime(i-1) is not known,
it is much less efficient (and this shouldn't be a surprise), as
it has to go back to the largest j < i for which it knows
ithprime(j) and search from there. It doesn't go all the way
back to 1, because it starts out with a remember table storing 292
values of ithprime. But still, if you want say ithprime(49998)
it has to go check all the odd numbers from ithprime(49399)+2 =
603919 to ithprime(49998) = 611939.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Fl...@safebunch.com
Table[Prime[i],{i,1,50000}]
It took 1.6 seconds on a PIII 600 MHz Windows NT 4.0 machine for 50000.
Doing the first 100000 took a whole 3.5 seconds.
I'll email you the list if you'd like.
Wilson
In article <9k9q8m$28e$1...@nntp.itservices.ubc.ca>, Robert Israel says...
The Scarlet Manuka
> This works really well; on the SUN Ultra 10 (300 MHz) in my office, it
> takes less than two minutes. The next 50000 primes take significantly
> more time -- about 8 1/2 minutes --, but this is still quite reasonable.
> This shows that Maple's "nextprime" is much more efficient than
> "ithprime" in finding prime numbers, which comes as kind of surprise.
I don't see why; once you get significantly past the list, each call
to ithprime has to determine all the previous primes past the list too.
Using nextprime means you only need to determine one more prime on each
call. So the results you report are what I would expect.
--
The Scarlet Manuka
E. Clark
>
> I don't see why; once you get significantly past the list, each call
> to ithprime has to determine all the previous primes past the list too.
> Using nextprime means you only need to determine one more prime on each
> call. So the results you report are what I would expect.
Actually, after the 25th prime in Maple 6, ithprime invokes the
recursive procedure `ithprime/small` which creates a remember table.
So it doesn't have to determine all previous primes. Maple 6 to begin
with has builtin a rather large table of values the largest of which
is
ithprime(22299999) = 36447497,
op(4,evalf(`ithprime/large`)); will give the full table. So even at
the beginning it doesn't have to go all the way back to the beginning
to find the next prime.
Carl DeVore
On 2 Aug 2001, E. Clark wrote:
> Actually, after the 25th prime in Maple 6, ithprime invokes the
> recursive procedure `ithprime/small` which creates a remember table.
> So it doesn't have to determine all previous primes. Maple 6 to begin
> with has builtin a rather large table of values...
736 entries may seem rather large when you are reading through it, but I
don't think it is large considering the problem.
>... the largest of which is
> ithprime(22299999) = 36447497,
>
> op(4,evalf(`ithprime/large`)); will give the full table.
Just a typo... That should be "eval" not "evalf". I'm sure you know.
> So even at the beginning it doesn't have to go all the way back to the
> beginning to find the next prime.
That list seems like it is set up for idle curiosity. People want to know
"What is the 100,000th prime?", etc. It is mostly one less than round
numbers. I'm just guessing here... there may be more strategy to it than
that. I would guess that for the vast majority of randomly selected
"small" integers (under 23 million), ithprime has to go fairly far back.
E. Clark
[Speaking of the remember table for the procedure `ithprime/small`
which is used by the procedure ithprime in Maple 6.]
>
> That list seems like it is set up for idle curiosity. People want to know
> "What is the 100,000th prime?", etc. It is mostly one less than round
> numbers. I'm just guessing here... there may be more strategy to it than
> that. I would guess that for the vast majority of randomly selected
> "small" integers (under 23 million), ithprime has to go fairly far back.
>
>
The idea is to precompute a large number of values of
`ithprime/small` spread out more or less evenly up to around 23
million -- but less dense as the numbers increase. Then when computing
`ithprime/small`(i) one steps back recursively till one reaches an
index in the table. The fartherest back one must go is bounded by the
size of the largest gap between the precomputed values in the remember
table. For example
if we trace the behavior of `ithprime/small`(35) we get:
trace(`ithprime/small`):`ithprime/small`(35);
{--> enter ithprime/small, args = 35
{--> enter ithprime/small, args = 34
{--> enter ithprime/small, args = 33
{--> enter ithprime/small, args = 32
{--> enter ithprime/small, args = 31
{--> enter ithprime/small, args = 30
{--> enter ithprime/small, args = 29
{--> enter ithprime/small, args = 28
{--> enter ithprime/small, args = 27
value remembered (in ithprime/small): ithprime/small(26) -> 101
<-- exit ithprime/small (now in ithprime/small) = 103}
<-- exit ithprime/small (now in ithprime/small) = 107}
<-- exit ithprime/small (now in ithprime/small) = 109}
<-- exit ithprime/small (now in ithprime/small) = 113}
<-- exit ithprime/small (now in ithprime/small) = 127}
<-- exit ithprime/small (now in ithprime/small) = 131}
<-- exit ithprime/small (now in ithprime/small) = 137}
<-- exit ithprime/small (now in ithprime/small) = 139}
<-- exit ithprime/small (now at top level) = 149}
149
It seems that the procedure has been changed somewhat for Maple 7. In
Maple 7 ithprime uses two procedures: `ithprime/small` and
`ithprime/large` . I haven't looked at them carefully, but I imagine
the principle is the same.
Edwin Clark
------------------------------------------------------------
W. Edwin Clark, Math Dept, University of South Florida,
http://www.math.usf.edu/~eclark/
------------------------------------------------------------