mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2007-10-12, 17:23   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13×19×23 Posts
Default 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
henryzz is offline   Reply With Quote
Old 2007-10-12, 17:40   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3×3,767 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
ewmayer is offline   Reply With Quote
Old 2007-10-12, 17:58   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

432210 Posts
Default

Quote:
Originally Posted by henryzz View Post
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/
petrw1 is offline   Reply With Quote
Old 2007-10-12, 18:22   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

326510 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2007-10-12, 19:08   #5
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

23010 Posts
Default

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.
Jens K Andersen is offline   Reply With Quote
Old 2007-10-12, 22:45   #6
Garman
 

22×1,669 Posts
Default

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
  Reply With Quote
Old 2007-10-13, 09:38   #7
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2×712 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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

Last fiddled with by xilman on 2007-10-13 at 09:38 Reason: Fix speeling misteaks
xilman is offline   Reply With Quote
Old 2007-10-13, 13:33   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2007-10-13, 14:32   #9
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Mr. P-1 is offline   Reply With Quote
Old 2007-10-13, 14:41   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

93616 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
wblipp is offline   Reply With Quote
Old 2007-10-13, 16:12   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5·571 Posts
Default

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.
ATH is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:58.

Sun Jul 12 07:58:21 UTC 2020 up 109 days, 5:31, 0 users, load averages: 1.76, 1.79, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.