I'm not sure how much longer I will be awake so I will advance onto the next topic and that is:
How do we store very large numbers?
The first thing we need to identify is how large is our number?
Thinking in terms of bits here(binary) we can arrive at the following equation:
The max number stored per bit
is: 2^n - 1
4 bits: 15
8 bits: 255
16 bits: 65,535
32 bits: 4,294,967,295
64 bits: 18,446,744,073,709,551,615
This leads us to our next point which is: Do we need signed numbers? (Do we need negative values?)
If yes we still can store the same number of numbers but we have to assign a range to them:
4 bits: -8 to 7
8 bits: -128 to 127
16 bits: –32,768 to 32,767
32 bits: –2,147,483,648 to 2,147,483,647
64 bits: –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
Note: by default most languages assume you are using signed numbers unless you specify.
In the case of c++ just add unsigned prior to the variable declaration like so:
unsigned int x;
Taking everything listed above into account lets look at the problem once again:
We need to store: 600,851,475,143
Comparing this to the charts above it is quite clear that we need to use a 64 bit value regardless of if we decide to be signed or unsigned.
There are a few options to accomplish this easily in c++ and that is by changing the data type from long(32 bit) to something larger like:
int64_t(64bits) or
long long(32-64bits).
In this case it is more memory efficient to use
long long as the number isn't a full 64 bits.
Simply put: change all your integer declarations to of type: long long and you should be set.
If you need to store even larger numbers than those described above you have to do some interesting things like creating your own data types and overloading basic operators... It's great fun :hysterical:
Anyway, did I make that clear? Sorry if it was a little over-kill, I don't know your experience so it's better to be safe than sorry.
Here is one solutions using your code:
Note: the findIfPrime function doesn't really need to support long long as it only ever sees the sqrt() of a long long -> sqrt(2^64) = 2^32