Printing large prime number

[scientist]

Any one knows how to print prime number of large number of digits about 1000 digits

[Ispil]

Print, or calculate?

[shadowmouse]

If you want to calculate large prime numbers, try the Sieve of Eratosthenes.

[E0p9LyTq]

@shadowmouse,

Can C++ deal with an integer of 1000 or more digits as easily as the other built-in integral types? Without resorting to a custom library?

[shadowmouse]

No, you have to get a bignum library to deal with numbers that large. As far as I know, the best way to find consecutive prime numbers is the sieve of eratosthenes, but I think there is a formula as well. Wikipedia has an article on it if you google prime formula.

EDIT: I really should have originally read the topic better. For the sieve to work, you need to be able to create a bitset of length of the largest number which you want to check whether it is prime.

[E0p9LyTq]

I read the wiki article on the sieve, that is why I asked if C++ had native support for large integers.

I also found several libraries that support large integers/big numbers, but a quick look at their respective webpages I can't find how many digits they support.

More research is needed, obviously.

[Ispil]

Well, he says he wants a large prime. He doesn't say that it has to be a consecutive one.

Key thing here- given n is a natural numbers, the product of all primes less than n, plus one, is prime. You wouldn't even need 1000 primes for their product to be over 1000 digits. Then just add one.

[Duthomhas]

You don't need to compute all primes -- just pick any large, odd number and test for primality with at least two different algorithms (preferably three).

If it is not prime, add two and try again. Repeat until prime.

I recommend the Baille-PSW test, or at minimum, the Miller-Rabin.

[helios]

I also found several libraries that support large integers/big numbers, but a quick look at their respective webpages I can't find how many digits they support.

An arbitrary precision (or "bignum") arithmetic library supports integers of any size, as long as they fit in the memory the library is designed to use. For example, a library designed to operate on integers stored in a hard drive can handle integers at around 2.6 billion decimal digits per gigabyte.

[Ispil]

Just checked; the product of the first 1000 primes is over 3000 digits long. So in regards to complexity, you're either generating a list of primes using a method that, most likely, will be O(N) then multiplying them all together (N operations) and add 1, yielding N^2; then again, in this case, N would be quite small (you don't even need 1000 primes). Or, you deal with testing random 1000 digit numbers for whether they're prime, which, depending on the algorithm, is going to be something along the lines of O(k * log^3(n)), though possibly more depending on the test.

I'd like to think that testing arbitrary 1000 digit numbers for primeness is going to be a lot less efficient than calculating a bunch of primes under a rather small upper limit (under 8000), multiplying them all together, and adding one. It may not be a truly "random" prime, but it's going to be a lot more computationally straightforward to do.

[E0p9LyTq]

@helios,

Thank you for the clarification. :)

[48T7M4Gy]

RSA-1978 encryption involves the product of two primes each of 100 digits long resulting in a key-related value of about 200 digits long which is quite a mean number. So anyone who has the know-how to rapidly ( or even slowly ) check the primality of 1000 digit numbers then might I suggest them applying immediately for a job with the NSA. That person will be a very valuable asset to them in a very short time if it's right.

As far as the sieve is concerned a single 1000 digit number is a trivial amount of storage space. However the sieve requires more than just that number alone to be stored - enough to forget about the sieve as any sort of solution unfortunately. In short, Eratosthenes doesn't scale up.

[48T7M4Gy]

http://primes.utm.edu/curios/index.php?start=301&stop=1000

[Duthomhas]

@Ipsil
Your checking wasn't very complete. In terms of complexity:
- Generating an arbitrary even large prime is O(n).
- Generating a probable large prime is, at worst, O(n²)
- Algorithms to multiply large primes are better than O(n²), so generating a probable large prime is better than O(n²)
- Space is O(n) [O(2n)]
- Adding 2 to a large number is an O(n) operation, in space O(1).

Using a straight-up Sieve is well known to be inefficient once you are outside of machine word size. Why?
- Division is the most expensive operation you can perform on large numbers
- (It is the most expensive operation you can perform, period.)
- The Sieve uses division to test every 'next' number for primality
- (Hey, we're adding 2 to our failed primes again, except we're doing it for every number instead of just a few. Hmm...)
- Dividing N large numbers will be, at worst, O(nⁿ)
- (Although, again, you can reduce that somewhat by an efficient division, but not by much more than turning them into multiplications, and the conversion step is not free.)
- Space becomes O(nⁿ)

Algorithms to determine primality are well-known and very efficient in comparison.

Further, you are mixing basic operations, which I think is disingenuous. If you are going to count multiplying a large prime as N operations (a gross simplification), then you also have to count creating a large prime as O(1). Doing otherwise is nothing more than twisting "facts" to confuse those who don't know any better.

Given the choice between using an inefficient division for every other number between 0 and N, and simply checking for a few numbers close to N with an efficient primality algorithm, I'll choose the latter every day of the week and twice on Sunday.


@scientist
Alas, I fear we have not answered your question.
Is this a homework assignment?
Or is this work-related.
If the latter, make sure to google around "bignums". The most popular one today is the GMP, which has functions both to create and manage large numbers themselves, but can also check primality for you.

Let us know what you want.

[48T7M4Gy]

The sieve doesn't use division. In fact it doesn't do any calculation. It sieves.

Where it strikes problems in scaling up is the size of the container to hold all the numbers. All the primes from 2 to n requires storage for all those numbers.

[shadowmouse]

However as Ipsil said, you don't need a big sieve in order to make a massive prime using the product of all previous primes + 1 rule, hence the only operations you are doing are additions (move along the sieve and adding 1 at the end), bit flipping (setting an element to not prime), and multiplication (product of all the primes). As far as I know, none of these take a long time.

[48T7M4Gy]

There's no question division isn't required. And there's no question about the multiplayer + 1 rule, at least in principle. Both of those are easily proved, the first by actually sieving and the second by a near trivial proof.

So if the sieve isn't so big claim is true can you show us?

[shadowmouse]

Assuming you know the size of the sieve you want, all you need is an std::bitset of that size. Because it is only 1 bit per element in a bitset (each element is a flag of whether that number is prime) then it is n/8 bytes, which isn't many seeing as people have gigabytes of RAM. If what Ipsil says about the product of the first 1000 primes being over 3000 digits, then you need at maximum 125 bytes for the sieve itself.

[48T7M4Gy]

125 bytes? So show us! Can I ask whether you have ever used the sieve?

[shadowmouse]

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<1000> sieve;
    for(unsigned i (0); i < 1000; ++i) {
        sieve[i] = 1;
    }

    for(unsigned i (2); i < 1000; ++i) {
        for(unsigned j (2*i); j < 1000; j += i) {
            sieve[j] = 0;
        }
    }

    for(unsigned i (0); i < 1000; ++i) {
        if(sieve[i] == 1) {
            std::cout<<i<<std::endl;
        }
    }

    return 0;
}

That prints the primes under 1000. I don't have a bignum library so I haven't written it multiplying them together, but you just have to replace printing with multiplying an accumulating variable. Then you just increment.

EDIT: I was a slight idiot. That is the first 1000 numbers, not primes (it's 170 primes). If you replace the 1000 with 10000, then it is 1231 primes and you can use those. That means it is 1250 bytes for the sieve. It takes my laptop 1-2 seconds to calculate and print those, so it's not overly slow.