unlimited (or very high) length integer storage

Question

Hello, as a side project I am working on some home-baked prime generation problems, trying to write some different implementations as a means of teaching myself C and C++. Of course, the quickest way to generate low primes is to already have them, so I want to go about setting up a hard disk prime list data file. I want to write all the code that generates primes, but I have no qualms about using already made storage methods. I have very little experience when it comes to actual coding, but understand most of the theory. (note that for most of this I will be talking about mathematical integers, rather than the int variables)

So I have some questions to ye, the experts:

1) The naive approach would just be to binary-write the integers as they are generated. However, in my head I imagine a list with items separated by some sort of flag, so that integers larger than 32 bits can be stored (if I get to that point). This is obviously inefficient, but something where the raw data for the array [4723, 12782, 8357] would look like 4723F12782F8357 that is, numbers are stored in base ten with 16 bits per digit and separated by F's. Obviously the data for ABCDE digit possibilities would be unused, so it's not a very efficient system, but you see what I mean. This would also make more and more sense as numbers get longer, since any in any fixed-length system the smallest entry would have to be as big as the largest. I'm sure there has to be something already written in C or C++ that does this efficiently.

2) Another possibility is a length-declaration system, where before each integer is stored, a fixed-length (lets say 1 byte) piece of data declares how long the integer is going to be (in bits). This obviously confers similar advantages to the previous option, with the added bonus of not wasting digit possibilities.

Does anyone know of how one would go about storing this kind of data? Is there a variable type I can store primes in so as not to run into size limits? Even better, what is the most efficient way to store a simple list of integers to hard disk in an easily retrievable format?

Answer 1

Don't reinvent the wheel. If you're dealing with large primes, you almost certainly want a BigNum library, such as GMP (http://gmplib.org/). GMP BigNums have serialization methods, so you can use those to easily write them to disk and read them from disk, leaving you free to think about the algorithm.

Answer 2

Using the g++ compiler on Ubuntu, I found that long int was 32 bits and long long int 64.

I was calculating perfect number from known Mersenne primes, holding the numbers in varying length arrays of long int; that means you can use long long int for scratch variables when doing long multiplication, long division, etc. I also confined the values in each long to be not more than 999,999,999, which makes it easy to print the answer.