downloading primes?

mnh001 · 2015-02-06, 00:04

I've noticed on factordb that you can download primes but only 5000 at a time. It would
take forever to get them all that way. Is there a way to download all 100M+ at once? And in text format?

Uncwilly · 2015-02-06, 00:15

Quote:

Originally Posted by mnh001

I've noticed on factordb that you can download primes but only 5000 at a time. It would
take forever to get them all that way. Is there a way to download all 100M+ at once? And in text format?

To what end? The first few million can be rapidly generated when needed.

mnh001 · 2015-02-06, 09:10

Just an experiment I'd like to try where I need all of them. I know I can generate the first few million easily but
to generate them all myself would also take forever.

Mini-Geek · 2015-02-06, 14:52

Quote:

Originally Posted by mnh001

Just an experiment I'd like to try where I need all of them.

There are an infinite number of primes (as you may know), and factorDB's are generally only of interest because they are known as factors of numbers. Why are you interested in factorDB's primes in particular? I suspect that you're not really, and are just asking the wrong question, which should be something like "how can I quickly generate a list of x primes with y-z digits?"

By the way, all of their primes are 126GB. Are you really prepared to deal with that much data?

LaurV · 2015-02-06, 15:18

Quote:

Originally Posted by Mini-Geek

By the way, all of their primes are 126GB. Are you really prepared to deal with that much data?

Huh? Only?

You can generate 200GB of primes in a night**, with a pari line like "n=1; while(1,write("primefile.txt", n=nextprime(n+1)))" or something equivalent. In the morning your HDD will be full and the windoze stuck with "low disk space".

edit **well, joking apart, you would need SSD or a ramdisk program, I just tried and can't write more than 5-6MB/minute, so this would mean about 3-4GB all night,

danaj · 2015-02-06, 20:52

I used forprime(p=2,10^8,write("primefile.txt",p)) to an SSD and only get about 1.2 MB/s (5.8M primes in 42 seconds).

Using perl -Mntheory=forprimes -E 'forprimes { say } 10**8' >primefile.txt completes in 2 seconds for 23.3 MB/s.

Using primesieve -p1 1e8 >primefile.txt takes 4.7 seconds for 10.4 MB/s.

Using a trivial odd-only SoE in C plus buffered I/O takes only 0.51 seconds for 95.4 MB/s. About 73 MB/2 for 10^9.

The slowest prime generator is the fastest to output, while prime sieve (the fastest sieve by far) isn't that great for printing. Printing takes more time than sieving as long as it's reasonable.

mnh001 · 2015-02-06, 23:41

Actually, my idea was a pre-test for factoring difficult composites.

A number may have a factor in common with another, which may have already been
done and entered in factordb. I did a speed test to try it out with the
numbers 2 to 100M in a text file. I chose a large prime (~30 digit) and
performed a mod test using the numbers in the text file.

It completed the test in 9 min 21 sec. Granted the primes in factordb are
a lot larger than my test numbers but I was just looking for a general
time frame.

If the computer is going to be spending weeks or months trying to factor
a difficult composite then doing this pre-test for 10 min or so could be
well worth it.

And since factordb already has primes over a very large range... who knows.

danaj · 2015-02-07, 00:01

Just for fun, I ran some more tests, this time to 10^10 (ASCII output is 4,948,214,537 bytes). Clearly this would be faster in binary, but the OP wanted text output, so why not. On a 1 month old Macbook Pro.

Code:

  202.91 MB/s   primegen + my buffered I/O
  171.14 MB/s   Perl/ntheory segmented sieve + my buffered I/O
   62.24 MB/s   Simple SoE + my buffered I/O
   23.66 MB/s   Perl/ntheory from Perl
   18.27 MB/s   primegen 0.97 from Atkin
   10.94 MB/s   primesieve 5.4.1

Bernstein's code is slightly faster than my segmented SoE, and both are much faster than the trivial odd-only SoE. All those with same I/O routines. Standard Perl or Bernstein's putchar stuff is slower, and primesieve using standard printf really cuts down the speed since it is the fastest at actually generating.

Anyway, 200GB of primes shouldn't take too long to generate, albeit they're consecutive primes rather than the ones from factordb. For actual use in a factoring or primality routine, of course you wouldn't want them printed in an ASCII file, so all these numbers are moot (but it was fun to look at).

For pretest, I suggest using mpz_gcd with a primorial and/or a tree sieve. Jens Kruse Andersen has a nice description of the latter. It is quite a bit faster than using mpz_divisible_ui_p once above a certain size. I'm sure others will also have thoughts of time spent in trial division vs. time with Rho, p-1, and ECM -- those are all quite good at finding small factors, and for numbers you're spending months on, you've probably run them already, making small factors that slipped through very unlikely. For checking random large primes, unless there is some reason to suggest those numbers have a good chance of occurring, it seems quite wasteful.

mnh001 · 2015-02-07, 00:08

True it probably is wasteful but since it will only take a very short time I figure it'll be worth it. I've spent
hours running yafu only to have it tell me that yes the number is composite.

Mini-Geek · 2015-02-07, 00:32

Quote:

Originally Posted by mnh001

Actually, my idea was a pre-test for factoring difficult composites.

A number may have a factor in common with another, which may have already been
done and entered in factordb. I did a speed test to try it out with the
numbers 2 to 100M in a text file. I chose a large prime (~30 digit) and
performed a mod test using the numbers in the text file.

A number is more likely to have smaller primes as factors. Thus, the most profitable primes to try are not "what's in factordb", but "the next smallest prime I haven't tried yet.
This is usually known as "trial factoring" (TF). As an early stage in finding primality or finding factors, it is the best. But you would not use it for large (e.g. >2^32) numbers.

Quote:

Originally Posted by mnh001

If the computer is going to be spending weeks or months trying to factor
a difficult composite then doing this pre-test for 10 min or so could be
well worth it.

And since factordb already has primes over a very large range... who knows.

Factordb has some large-ish primes, which are not useful for TF. It does not necessarily have all small primes.
With the right program, you can generate small primes faster than you can read them from disk, so besides being unwieldy to download or store such large files, it is not useful.

mnh001 · 2015-02-07, 00:43

Yes, I know. But like I said this was just going to be an experiment. If I'm trying to factor HP49(119) (which has 2 small
factors 73 and 16249 plus a C251) I'm pretty sure the smallest factor of the c251 has quite a few digits.

What I'm gathering is that there isn't a way to get the factordb primes in one chunk. No problem. I'll just come up with
another experiment.

2015-02-06, 00:04	#1
mnh001 Apr 2011 2⁶ Posts	downloading primes? I've noticed on factordb that you can download primes but only 5000 at a time. It would take forever to get them all that way. Is there a way to download all 100M+ at once? And in text format?

2015-02-06, 20:52	#6
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 38C₁₆ Posts	I used forprime(p=2,10^8,write("primefile.txt",p)) to an SSD and only get about 1.2 MB/s (5.8M primes in 42 seconds). Using perl -Mntheory=forprimes -E 'forprimes { say } 10*8' >primefile.txt completes in 2 seconds for 23.3 MB/s. Using primesieve -p1 1e8 >primefile.txt takes 4.7 seconds for 10.4 MB/s. Using a trivial odd-only SoE in C plus buffered I/O takes only 0.51 seconds for 95.4 MB/s. About 73 MB/2 for 10^9. The slowest prime generator is the fastest to output, while prime sieve (the fastest sieve by far) isn't that great for printing. Printing takes more time than sieving as long as it's reasonable. Last fiddled with by danaj on 2015-02-06 at 20:52*

2015-02-07, 00:01	#8
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	Just for fun, I ran some more tests, this time to 10^10 (ASCII output is 4,948,214,537 bytes). Clearly this would be faster in binary, but the OP wanted text output, so why not. On a 1 month old Macbook Pro. Code: 202.91 MB/s primegen + my buffered I/O 171.14 MB/s Perl/ntheory segmented sieve + my buffered I/O 62.24 MB/s Simple SoE + my buffered I/O 23.66 MB/s Perl/ntheory from Perl 18.27 MB/s primegen 0.97 from Atkin 10.94 MB/s primesieve 5.4.1 Bernstein's code is slightly faster than my segmented SoE, and both are much faster than the trivial odd-only SoE. All those with same I/O routines. Standard Perl or Bernstein's putchar stuff is slower, and primesieve using standard printf really cuts down the speed since it is the fastest at actually generating. Anyway, 200GB of primes shouldn't take too long to generate, albeit they're consecutive primes rather than the ones from factordb. For actual use in a factoring or primality routine, of course you wouldn't want them printed in an ASCII file, so all these numbers are moot (but it was fun to look at). For pretest, I suggest using mpz_gcd with a primorial and/or a tree sieve. Jens Kruse Andersen has a nice description of the latter. It is quite a bit faster than using mpz_divisible_ui_p once above a certain size. I'm sure others will also have thoughts of time spent in trial division vs. time with Rho, p-1, and ECM -- those are all quite good at finding small factors, and for numbers you're spending months on, you've probably run them already, making small factors that slipped through very unlikely. For checking random large primes, unless there is some reason to suggest those numbers have a good chance of occurring, it seems quite wasteful.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Distribution of Mersenne primes before and after couples of primes found	emily	Math	34	2017-07-16 18:44
Downloading prime	nekketsu	Software	1	2007-12-17 02:25
Downloading and printing Mersenne Primes	PrimeCrazzy	Lounge	5	2005-12-30 16:48
Downloading Maths	devarajkandadai	Miscellaneous Math	0	2004-08-12 06:02
Trouble Downloading Factoring File	jeff8765	Lone Mersenne Hunters	2	2003-07-16 16:30

2015-02-06, 09:10	#3
mnh001 Apr 2011 2⁶ Posts	Just an experiment I'd like to try where I need all of them. I know I can generate the first few million easily but to generate them all myself would also take forever.

2015-02-06, 23:41	#7
mnh001 Apr 2011 2⁶ Posts	Actually, my idea was a pre-test for factoring difficult composites. A number may have a factor in common with another, which may have already been done and entered in factordb. I did a speed test to try it out with the numbers 2 to 100M in a text file. I chose a large prime (~30 digit) and performed a mod test using the numbers in the text file. It completed the test in 9 min 21 sec. Granted the primes in factordb are a lot larger than my test numbers but I was just looking for a general time frame. If the computer is going to be spending weeks or months trying to factor a difficult composite then doing this pre-test for 10 min or so could be well worth it. And since factordb already has primes over a very large range... who knows.

2015-02-07, 00:08	#9
mnh001 Apr 2011 2⁶ Posts	True it probably is wasteful but since it will only take a very short time I figure it'll be worth it. I've spent hours running yafu only to have it tell me that yes the number is composite.

2015-02-07, 00:43	#11
mnh001 Apr 2011 100₈ Posts	Yes, I know. But like I said this was just going to be an experiment. If I'm trying to factor HP49(119) (which has 2 small factors 73 and 16249 plus a C251) I'm pretty sure the smallest factor of the c251 has quite a few digits. What I'm gathering is that there isn't a way to get the factordb primes in one chunk. No problem. I'll just come up with another experiment.