Finding primes from 1 upwards

henryzz · 2007-10-12, 17:23

has anyone seached exhautively for primes particularly high
i have seached the web but cannot find any projects

if not what would be the best method for starting this search

ewmayer · 2007-10-12, 17:40

Quote:

Originally Posted by henryzz

what would be the best method for starting this search

Well, starting from 2 rather than 1 would probably be a good idea.

Now that I've done half the work for you and found the largest even prime, I'll let you do the odds.

petrw1 · 2007-10-12, 17:58

Quote:

Originally Posted by henryzz

has anyone seached exhautively for primes particularly high
i have seached the web but cannot find any projects

if not what would be the best method for starting this search

I wrote a program a few years ago based on the Seive Of Eratosthenes. Due to memory limitations of the program I used (BASIC

) I had to stop at about the number 6 Billion. It only took about a day to run on a P3 400Mhz.

There are some links to lists here: http://primes.utm.edu/lists/small/

bsquared · 2007-10-12, 18:22

I guess it depends by what you mean by "particularly high". Here: http://www.ieeta.pt/~tos/primes.html, tables of pi(x) (the number of primes less than x) are given, and have been found/verified by the sieve of eratosthenes. It would be impractical/useless to write down all these primes. For instance, he gives pi(10^23) = 1925320391606803968923, which would take something like 17087218 peta bytes of storage if you wanted to list them all.

If you want to help find the biggest known primes, join GIMPS.

Jens K Andersen · 2007-10-12, 19:08

pi(x) can be computed much faster than computing all primes up to x. Only some of the pi(x) values up to pi(10^23) have been verified by the sieve of Eratosthenes. The largest exhaustive computation of primes is part of the Goldbach conjecture verification at http://www.ieeta.pt/~tos/goldbach.html. They reached 10^18 in April. pi(10^18) = 24,739,954,287,740,860 is also far too many primes to store. They were only kept shortly in ram.

2007-10-12, 22:45

Hmm, my old account (think of years, not month) is not active any more... anyways:

I still find this text about the practical limitations of computing and saving all primes to be rather good. It starts easy, but at the end it goes into detail about the limits of todays technologies. (clustering techniques etc. and where is will fail)
http://www.troubleshooters.com/codec...imenumbers.htm

xilman · 2007-10-13, 09:38

Quote:

Originally Posted by ewmayer

Well, starting from 2 rather than 1 would probably be a good idea.

I guess so, but the additional work saved is insignificant.

Here's a list of primes from 14 upwards: 17, 19, 23, 29, ...

I'll leave you to find the primes from 1 to 14.

Paul

henryzz · 2007-10-13, 13:33

so how much disk space would it take to store the first 1,000,000 primes
i have previously written a vb.net program which uses the sieve of Eratosthenes to find all primes up to 2^30
it took about 90 second to run
my program doesnt work any higher than that because the index for a bitarray has a max of (2^31)-1

Mr. P-1 · 2007-10-13, 14:32

Quote:

Originally Posted by henryzz

so how much disk space would it take to store the first 1,000,000 primes

As a text file: Less than 8MB. In fact I keep the first 4,630,913, primes (up to 79,299,959) in a 40MB text file as I have a script which uses it.

wblipp · 2007-10-13, 14:41

Quote:

Originally Posted by henryzz

so how much disk space would it take to store the first 1,000,000 primes

You could download them and see.

http://www.rsok.com/~jrm/printprimes.html

ATH · 2007-10-13, 16:12

I have a file taking 285,714,288 bytes with all primes up below 10,000,000,080 using the 48 bit / 210 integers format.

2007-10-12, 17:23	#1
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 16F8₁₆ Posts	Finding primes from 1 upwards has anyone seached exhautively for primes particularly high i have seached the web but cannot find any projects if not what would be the best method for starting this search

2007-10-12, 18:22	#4
bsquared "Ben" Feb 2007 3×1,171 Posts	I guess it depends by what you mean by "particularly high". Here: http://www.ieeta.pt/~tos/primes.html, tables of pi(x) (the number of primes less than x) are given, and have been found/verified by the sieve of eratosthenes. It would be impractical/useless to write down all these primes. For instance, he gives pi(10^23) = 1925320391606803968923, which would take something like 17087218 peta bytes of storage if you wanted to list them all. If you want to help find the biggest known primes, join GIMPS. Last fiddled with by bsquared on 2007-10-12 at 18:23

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Finding VERY large primes	c10ck3r	Information & Answers	34	2012-08-29 16:47
Why arent there many softwares for finding Huge Primes	blistervol	Math	2	2012-08-20 17:26
Best Work for Finding Primes	Unregistered	Information & Answers	9	2012-06-24 13:50
Finding primes using modular stacking	goatboy	Math	1	2007-12-07 12:30
Finding primes with a PowerPC	rogue	Lounge	4	2005-07-12 12:31

2007-10-12, 19:08	#5
Jens K Andersen Feb 2006 Denmark E6₁₆ Posts	pi(x) can be computed much faster than computing all primes up to x. Only some of the pi(x) values up to pi(10^23) have been verified by the sieve of Eratosthenes. The largest exhaustive computation of primes is part of the Goldbach conjecture verification at http://www.ieeta.pt/~tos/goldbach.html. They reached 10^18 in April. pi(10^18) = 24,739,954,287,740,860 is also far too many primes to store. They were only kept shortly in ram.

2007-10-12, 22:45	#6
Garman 2·3²·17·23 Posts	Hmm, my old account (think of years, not month) is not active any more... anyways: I still find this text about the practical limitations of computing and saving all primes to be rather good. It starts easy, but at the end it goes into detail about the limits of todays technologies. (clustering techniques etc. and where is will fail) http://www.troubleshooters.com/codec...imenumbers.htm

2007-10-13, 13:33	#8
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³×3×5×7² Posts	so how much disk space would it take to store the first 1,000,000 primes i have previously written a vb.net program which uses the sieve of Eratosthenes to find all primes up to 2^30 it took about 90 second to run my program doesnt work any higher than that because the index for a bitarray has a max of (2^31)-1

2007-10-13, 16:12	#11
ATH Einyen Dec 2003 Denmark 6127₈ Posts	I have a file taking 285,714,288 bytes with all primes up below 10,000,000,080 using the 48 bit / 210 integers format.