Prime Number generation

[np complete]

I'm coding a encryption program where I need to generate random prime.
I wrote this code

for(i=3; i<10000000; i=i+2 )
    {
        for(j=2; j <= sqrt(i); j++ )
        {
            if(!(i%j)) break;
        }

        if (j>sqrt(i))
        {
            cout<<i << " ";
        }
    }

This tests a number till is square root. Its good for small prime numbers. But encryption needs prime of range 100 digit. But a 20 digit prime would be fine. How to do this ? I googled and found AKS algorithm, but I'm finding it difficult to code. So can anyone suggest some other algorithm ? And how to get a 20 digit prime.

[Taywin]

From what I glance at your code, are you sure that an int can handle 20 digit numbers? That may be the first problem you need to solve -- data type -- before you attempt to find a number...

[np complete]

I can use array, or linked list for storing 20 digit number.

[DeanMSands3]

Those work, but they tend to be slow.
Have you looked into Multi Precision Number libraries?
There's GMP and MPFR to name a few.
FYI: uint64_t will get you into the very shallow end of 20-digit numbers (i.e. 0-18446744073709551615)

[np complete]

FYI: uint64_t will get you into the very shallow end of 20-digit numbers (i.e. 0-18446744073709551615)

Do you mean long long x decleration ?

[NathanOliver]

If you want an unsigned 64 bit integer you can use unsigned long long foo;. Check this out to see the data types and their ranges. http://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.80%29.aspx

[Labdabeta]

There are a lot of those primes out there, but generating them will undoubtedly be slow... especially if you want the really big ones. I would suggest A) looking into an arbitrary arithmetic library (so that you can handle epicly large numbers) then B) google for lists of large numbers, there are tons of them. You could then store them in an array and randomly pick one from it. Another option is to store an array of ints representing valid exponents for Mersenne Primes, then just generate the corresponding prime.

[np complete]

Storing list of large prime is not my option. I want to generate prime. And Labdabeta, what do you mean by arbitrary arithmetic library ?

[WaltP]

And Labdabeta, what do you mean by arbitrary arithmetic library ?

Bad choice of words. He means a large-number arithmetic library? Arbitrary is not correct. You want to pick a package with care.

[pyTony]

Most used term is maybe multi-precission numbers. Be sure not to forget first to test candidates with pseudoprime test like http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html