# Thread: Storing a "large" number of prime numbers

1. ## 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.

2. 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.

3. 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.

4. 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

5. 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.

6. 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.

7. Thanks

Popular pages Recent additions