Database of Primes

[ogl...@yahoo.com]

Please let me know:

Is there a database of all known (consecutive) primes: {2,3,..,p_max}

And what is the length of the largest prime, in that sequence? (how
many digits)

If something like that you know that exist, I would ask you to provide
me with that known primes.

thank you,
very much.

[Virgil]

In article <1131240908.9...@z14g2000cwz.googlegroups.com>,
ogl...@yahoo.com wrote:

See, for example,
http://primes.utm.edu/

[ogl...@yahoo.com]

"The list of the 5000 largest known primes "

I quess that there are more than 5.000 known primes;
some better source?

thanks

[MuTsun Tsai]

Well if you're looking for a prime table, why don't you generate one by
yourself using math software such as Maple or Mathematica?

[Virgil]

In article <1131243013....@g43g2000cwa.googlegroups.com>,
ogl...@yahoo.com wrote:

Try Googling it for yourelf!

[Seán O'Leathlóbhair]

If you have the storage for the table then you can quickly and easily
calculate it. The sieve of Eratosthenes is easy to program and fast to
run. It should fill all of your available memory in a reasonable time.
Here's a simple tip to get the most of your storage:

Use a bit map since you only want to remember prime / not prime for
each number. This allows you a range of 8 * bytes available.

Don't bother with storage for even numbers. Hard code 2 and assume
that none of the other even numbers are prime. Now you have 16 * bytes
available.

Better still, work modulus 30 and you will find that only 8 of each
consecutive 30 numbers have any chance of being prime. So you can
store the status of 30 consecutive numbers in one byte. Now you have
30 * bytes available. Hence with 1Gb of memory you can get a list of
consecutive primes up to over 30 billion. (*)

If you have read up to this limit and want more, you can throw some of
the previous ones out. As long as you retain up to the square root of
your target, you can continue. So with 1Gb, you could produce of list
of primes up to 10^18 but not all of them would be in memory at once.
Letting this form of the program run to completion may take a long
time.

(*) Up to here, it is not speculation. I wrote this program in Java
once. It was easy and it did run quickly. For the sake of the
forests, I did not print the results.

--
Seán O'Leathlóbhair

[KBH]

'Primes from Composite Gaps' calculates primes up to 10^17 within numerical
blocks of 500...so that it is like stepping through sections of a list.

Here is a user link to the program:

http://www.kbhscape.com/prime.htm

[ogl...@yahoo.com]

Thank you for your answers.

Eratosten and something like that, doesn't work for me.

I am looking not up to couple of bilions, but for primes in a range of
maybe 30-50 digits;
if possible.

So, any new idea or coment; I strictly am encouraging you that we
continue with this discussions.

Thanks.

[LC Killingbeck]

ogl...@yahoo.com wrote in news:1131331530.364671.47100
@z14g2000cwz.googlegroups.com:

I have to ask! Which are you asking for:

(1) A list of ALL primes through 30-50 digits!!!
(2) Some primes of 30-50 digits.

The first is impossible. Really! Do you have any comprehension of how
many numbers that is? It won't fit on all the hard disks ever made, and
ever likely to be made before the extinction of mankind. (You are
still short of a "number of atoms in the universe" problem for
storage, though into a "life of the universe" problem in computation
time.)

The second is easy. Primes of 30-50 digits are easy to find. Just
generate an odd number with the desired number of digits, and test it
for primality. If it is not, just try another one at random. You will
find one pretty soon. ln(10^50) is around 117, so you will have to
test on average around that many odd numbers in the range. Lots of
people in this newsgroup can help you more with the details (e.g.,
existing software to test primality) than I can, if this is your problem.

So, can you clarify which of (1) or (2) you are needing? I'll repeat:
ALL of the primes from 2,3,5,... through some 30-50 digit number is
impossible in this universe. SOME 30-50 digits primes is easy.

Lynn Killingbeck

[Jyothirmai]

You can use OpenSSL library to generate primes of any length. It is very
easy to use if you have some programming experience.

-J

[ogl...@yahoo.com]

Unfortunatelly,
I needed (1).

[ogl...@yahoo.com]

Can you provide me with more info about that; I dont have the
experiance with OpenSSL.
Thanks

[LC Killingbeck]

ogl...@yahoo.com wrote in
news:1131509047....@o13g2000cwo.googlegroups.com:

> Unfortunatelly,
> I needed (1).
>

You can't have it! Now what? Where are you going to store it?!?! I've
seen terabyte disk drives on the shelves. That's 10^12 bytes. Assume
you can store each of your primes in 1 byte (you can't). Your list of
some 10^50/ln(10^50) = 8.7*10^47 bytes will take some 8.7*10^35 such
disk drives. If the world manufactures 10^10 such drives every year
(something like one for ever person on the planet per year), it will
take 8.7*10^25 years to manufacture them. The age of the universe is
a few billion years, say 10^12 to be generous. It will take some
87,000,000,000,000 times the entire life of the universe to make the
disks you say you need! I hope you are not in a hurry!

I bet some of the physics people can estimate how 10^50 relates to the
number of atoms in the earth. [Something around 10^80 in the entire
universe.]

I'll repeat: You can't have such a list, in this universe.

That was fun! It's been a while since I dashed off that kind of
back-of-the-envelope estimate, where a factor of a few billion
makes no difference to the conclusion.

Seriously, perhaps if you could describe what you are really trying
to accomplish, someone can help you with a practical solution. If
you can not change the problem to something feasible, no on can
help you. Perhaps something like a list of 10^6 50-digits primes?
That's possible. Even 10^9 (rough guessing, here, at 1 millisecond
per prime, 10^9 takes 10^6 seconds, around 28 hours). By 10^12, you
need years of time, and 1000's of terabyte drives. Make your own
space and time estimates, though.

Lynn Killingbeck

[Robert Israel]

In article <4370...@usenet.zapto.org>,
Jyothirmai <jyoth...@nospam.net> wrote:

|>You can use OpenSSL library to generate primes of any length. It is very
|>easy to use if you have some programming experience.

Or if you don't have programming experience, use a Computer Algebra System
such as Maple.

> nextprime(10^50);
100000000000000000000000000000000000000000000000151

(obtained in 0.016 seconds)

Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

[Dik T. Winter]

In article <1131509047....@o13g2000cwo.googlegroups.com> ogl...@yahoo.com writes:
> > (1) A list of ALL primes through 30-50 digits!!!
>

> Unfortunatelly,
> I needed (1).

You should start buying the hardware to store it.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[ogl...@yahoo.com]

OK. Thanks. Actually, now it is clear. It is impossible to store them
all.

The reason what initiated this discussion was:

I typed in Mathematica "give me 100th prime" it worked;
"give me 1000.000th prime" it also worked.

But, after some trying I figured out that on my computer ("normal PC")
I couldn't get n-th prime, for n sufficiently large.

So, the question is;

Ok, if I cannot store "all primes";

Can I calculate n-th prime, where n is extremly large?
Eg. 10^20-th prime; or so on you should have better sense for this
numbers (what is big what is not).

Thanks.

[ogl...@yahoo.com]

Particulary, what is the algorithm that Maple uses for caclulating the
nextprime?

Thanks

[Robert Israel]

In article <1131686873....@o13g2000cwo.googlegroups.com>,

<ogl...@yahoo.com> wrote:
>Particulary, what is the algorithm that Maple uses for caclulating the
>nextprime?

For nextprime(x), it checks the odd integers > x one by one using
isprime, which is a probabilistic primality testing routine. According
to the help page, this uses a strong pseudo-primality test and a Lucas
test. A number that passes the test is "very probably prime", but
strictly speaking hasn't been proven to be prime.

[Gerry Myerson]

In article <1131686873....@o13g2000cwo.googlegroups.com>,
ogl...@yahoo.com wrote:

> Particulary, what is the algorithm that Maple uses for caclulating the
> nextprime?

I imagine it just tests n + 1, n + 2, etc., until
it finds a number it believes to be prime.

If n is, say, a 100-digit number, then it is exceedingly unlikely
that Maple will have to check more than 1000 numbers before it
finds a prime.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[Gerry Myerson]

In article <1131686672.4...@z14g2000cwz.googlegroups.com>,
ogl...@yahoo.com wrote:

> Can I calculate n-th prime, where n is extremly large?
> Eg. 10^20-th prime; or so on you should have better sense for this
> numbers (what is big what is not).

I don't think it is feasible to calculate the 10^20-th prime.
However, it is easy to get a good estimate of where the 10-20th
prime ought to be, and then to find a prime that is pretty near
the 10^20th.

[Robert Israel]

In article <1131686672.4...@z14g2000cwz.googlegroups.com>,
<ogl...@yahoo.com> wrote:

AFAIK it is not possible to calculate this in a reasonable time, in
the current state of mathematical knowledge and computer hardware.
See <http://primes.utm.edu/nthprime/> which will calculate the n'th
prime for n up to 10^12.

[LC Killingbeck]

ogl...@yahoo.com wrote in news:1131686672.449190.110710
@z14g2000cwz.googlegroups.com:

You might find this site of interest. Taken from a google search, knowing
about "he who should not be mentioned lest he reawake!" back in 2002. It
does not tell _what_ the primes are, just _how many_. I'm not up to date
(or even much interested) in progress since that time, myself.

http://numbers.computation.free.fr/Constants/Primes/Pix/results.html

Shhhh! The troll is sleeping under the bridge! I hope I did not wake
him! Be very quite when you cross!

It does not answer your general question of "what is the n-th prime?".

Lynn Killingbeck

P.S. 4*10^23-93 is the largest prime less than 4*10^23. (MIRACL factor
program and a couple minutes mashing keys under DOS command line.)
Together with the cited site, that is the 783,964,159,847,056,303,858-th
prime.

[ogl...@yahoo.com]

Yes;) It doesn't answer my question for n-th prime.

Anyway, I know, it is hard.

[ogl...@yahoo.com]

Prof. Israel:

May I ask you for some references (books, articles) about:

"pseudo-primality test and a Lucas
test. A number that passes the test is "very probably prime""

Thanks.

[A N Niel]

In article <1131693147....@f14g2000cwb.googlegroups.com>,
<ogl...@yahoo.com> wrote:

Knuth (the art of computer programming) vol. 3, 2nd edition

[Larry Lard]

LC Killingbeck wrote:
[snip]

> You might find this site of interest. Taken from a google search, knowing
> about "he who should not be mentioned lest he reawake!" back in 2002.

He's not sleeping, it's just that he only posts now somewhere where no
one can answer back. If anything, his material is even better than it
used to be.

(No names, no URLs... if anyone doesn't know what we're talking about,
don't worry, you're happier for it)

--
Larry Lard
Replies to group please

[Pubkeybreaker]

Hi Gerry!

Actually, nailing down the 10^20 prime would not be that hard.
We already know pi(x) for x ~ 10^22 and can compute pi(x) for x near
4.6 x 10^21 with some, but not a lot of major difficulty. So just get
an
accurate estimate of the 10^20 prime via Rosser-Schoenfeld, then use
binary search by computing pi(x) for x in that neighborhood.

An even better method might be to compute pi(x) for x slightly smaller
than
the 10^20 prime, then sieve up to the 10^20 prime using x as a
starting point.

This would be a large, but feasible calculation.

Bob

[Pubkeybreaker]

"Knuth (the art of computer programming) vol. 3, 2nd edition"

Much better references (for this particular problem) would be:

Crandall & Pomerance, Prime Numbers: A computational perspective

Riesel , Prime Numbers and Computer Methods for Factorization

[ogl...@yahoo.com]

Thanks.

[ogl...@yahoo.com]

OK, thanks.

I'll start soon the topic, how can be calucated (how to be close to)
the N-th prime.