# Storing a "large" number of prime numbers

• 09-20-2012
javaeyes
Storing a "large" number of prime numbers
I have been writing some c code to investigate the properties of prime numbers. Currently I have a function getPrimes(int primemax) which dynamically allocates memory for an array of the primes, so that primes[0]=2 , primes[1]=3 .... This has been working well, but I am going to need a more permanent and scalable way to store them as primemax grows large. I am not opposed to using some service (if such a service exists) or to writing my own code to possibly store them as a csv list.
My future algorithm will constantly be needing to find primes[bignumber] where bignumber is the index of the primes array. The actual prime stored in that index will be even larger.
Any thoughts appreciated. Thanks.
• 09-20-2012
grumpy
Define what you mean by primemax being "large": how scalable do you need to be? Do you intend to go beyond what can be represented in a 32 bit unsigned int? Beyond what can be stored in a 64 bit unsigned integer?

It has actually been proven that there is an infinite number of prime numbers i.e. whatever value you pick, there will be a larger prime value. The largest known primes have millions of decimal digits.
• 09-20-2012
oogabooga
• 09-20-2012
javaeyes
I will need go beyond 64 bit unsigned integers, so I will need to use some sort of additional library at the least. I am beginning to think python might be an easier road, i've read that the int datatype has an arbitrary size. I've just started to get dialed into c and feel that under the hood it will be better to do it with c though.
And yes I am aware there are infinite primes, in fact it's one of my favorite proofs. (And possibly the only proof I have memorized)
And so "large" will mean 50-100+ decimal digits (for the prime values) dwarfing the default data size for ints-- the indexes on the other hand should be ~2% of the largest prime I'll need.
• 09-20-2012
oogabooga
Can you let us in on the purpose of your secret project? You'll get more pertinent advice that way.

Check out The GNU MP Bignum Library
• 09-20-2012
javaeyes
I am trying to factor large semi-prime numbers (prime multiplied by a prime.) You can probably do the math, and I realize that this may all be in vain, but it's a lot of fun and I'm learning a ton about other things I would never come across. And for the record I am doing it as a purely academic pursuit (though not for credit) in the sense that I am not trying to factor any one particular number to crack it, but to look at properties of all semi primes. I realize there is a >99% chance I will not find an algorithm better than current sieves. But that doesn't mean you can't try.
• 09-20-2012
oogabooga
I didn't mean to suggest that your efforts were futile. :) You sound like you understand the situation, and now we know exactly what you're trying to do.

Check out that bignum library.
• 09-20-2012
javaeyes
Thanks