Printing large prime number

[Ispil]

The product of all the first 350 primes (2 through 2357) plus one is:

237274539898702402624666173056940007
194085259853091370675096131309361301966113
666004330421495322958854911582423587938184
207710665300844015776348251582675589646328
198796197954333853067334428701846321901611
500491708849630608918998143786974606777881
970508665922660821490577326540652100582119
069616496676906278927060739246681041161136
492725142572409485319985546893045847245177
948573985064213772190943391807127437163646
778638320234065758308102119910289027855049
207505397066340210015319189355581314362919
932849450082201692637822657551431585564465
899014285700762014151216756895326084855921
732375597466149461662162548146972614148804
262860590400782855383511301086360227224638
854978167555473872028908128896218215890888
807489591263025349084879544273886986195949
216431109060075259894298560889652043388921
452984230337894356537833107708282104650439
293670804324270875203296897768353922535155
007754067147717307212218551412075831718604
843231693501323071579366124518691633498521
9768354365429487437645709510479749387571

which is exactly 1000 digits. You wouldn't even need to generate primes- you could just use a list of already-known ones, and if you want a bigger number, tack on the next few primes.

https://primes.utm.edu/lists/small/10000.txt is a list of the first 10000 primes, delimited by spaces and newlines. Copy-paste it into a document, save, and you can now generate primes up to... an absurd amount of digits.

At a minimum, this at least gives you a known prime of 1000 digits. Using various primality tests and the like, it should be reasonable to get to other primes relatively quickly from here.

[48T7M4Gy]

So, shadow you meant your sieve program is 125 bytes. Well done!

My comment relates to the size of sieve[j] and decimal rather than binary. But that's not an issue for me now that I understand where you're coming from. The non division confirmation is there to see too!

Ispil clearly demonstrates the ease by other means to get 1000 digits. The sieve would have a lot of trouble getting there I claim.

[shadowmouse]

I meant the bitset itself takes up 125 bytes, but that was an error on my part, the bitset takes 1250 bytes to find 1231 primes, which will then have a product of more than 3000 digits long, so it is less than that much.

[cire]

I meant the bitset itself takes up 125 bytes, but that was an error on my part, the bitset takes 1250 bytes to find 1231 primes

We can do better than that with a small optimization:

// http://ideone.com/RbUJBk
#include <bitset>
#include <iostream>
#include <vector>

template <std::size_t N>
struct prime_sieve
{
    prime_sieve() : _sieve()
    {
        _sieve.flip();
        
        for (std::size_t i = 0; i < N; ++i)
        {
            if (_sieve.test(i))
            {
                auto value = 3 + i * 2;
                for (std::size_t j = i + value; j < N; j += value)
                    _sieve.reset(j);
            }
        }
    }

    std::vector<unsigned long long> get_primes() const
    {
        std::vector<unsigned long long> primes(1, 2);
        for (std::size_t i = 0; i < N; ++i)
            if (_sieve.test(i))
                primes.push_back(3 + i * 2);

        return primes;
    }

private:
    std::bitset<N> _sieve;
};


int main()
{
    const std::size_t bits = 4000;

    prime_sieve<bits> sieve;

    auto primes = sieve.get_primes();

    std::cout << "Found " << primes.size() << " primes using " << bits / 8 << " bytes.\n";
    std::cout << "Last prime found: " << primes.back() << '\n';
}

But, I think your original point stands. The size of the sieve required is not all that large.

[Duthomhas]

Oops! I was thinking of Trial Divisions....

[48T7M4Gy]

Oops! I was thinking of Trial Divisions....

Well, there goes the job at the NSA - but the bright side is my credit card is still relatively prime and relatively safe.

[48T7M4Gy]

But, I think your original point stands. The size of the sieve required is not all that large.

There is a lot of difference between the storage for a trivial binary exercise that takes the first couple of prime numbers up to < 8000 and extrapolating that to 1000 digit numbers!

[ne555]

> given n is a natural numbers, the product of all primes less than n, plus one, is prime.
no, its factors may be greater than n.
By instance

$ factors 30030
30030: 2 3 5 7 11 13
$ factors 30031
30031: 59 509

[48T7M4Gy]

Slightly off the immediate topic but ...
https://en.wikibooks.org/wiki/Some_Basic_and_Inefficient_Prime_Number_Generating_Algorithms

[Ispil]

Yep, ne555's right. No surprise that there's no easy way to generate large primes.

[48T7M4Gy]

You are (obviously) right ne555.

A little searching reveals Euclid's Theorem which relies on this concept to show that there are infinitely many prime numbers. But that's a different thing, the theorem does not claim to generate prime numbers.

https://en.wikipedia.org/wiki/Prime_number.

[Ispil]

Yep. That sort of misinterpretation tends to happen when one only has a passing glance at the thing.

[48T7M4Gy]

However, if p and q are prime then ( p * q ) + 1 is not prime except in the cases where it is prime or otherwise fits in or out. Maybe this is where the misinterpretation comes from. Sounds good anyway.

[Ispil]

No, it wouldn't be prime- it would be relatively prime to p and q. Not the same thing. The misinterpretation was that I didn't realize that it was saying that N (product of all p<n)'s prime factors are all greater than n, not that N has only itself as a prime factor.

[48T7M4Gy]

Well, that little mishap has been expunged from the record. :-]

[48T7M4Gy]

1. Every integer greater than 1 is a product of primes.
2. Primes are integers.

Therefore,

3. Every prime is the product of integers.

[Ispil]

Natural numbers, but yeah; that's tautologically true. Primes are products of themselves and one; one is a natural number, and themselves are natural numbers. Hence, they are the product of natural numbers.

As for your correction to your post, it's also rather silly. "x is not prime except in the cases where it is prime..."

I think it's rather safe to say that primes are as unpredictable as we expect them to be.

[48T7M4Gy]

Don't take life too seriously. Just think there's probably a billion or so chinese who don't know about this discussion and even if they did I doubt they'd give a shit.

[Ispil]

Yep. I should also probably not post at 2 AM.

[48T7M4Gy]

:)