Prime Number Generation

[Shadow]

Hey all,

 

I just wanted to ask, I was thinking the other day and a though struck me.

 

Given a number [math]x \in N[/math], then [math]x[/math] will be prime if

 

[math]GCD(x\#,[/math] [math]x) = 1[/math],

 

where [math] GCD(a,b)[/math] is the greatest common divisor of [math]a,[/math] [math]b[/math], and [math]x\#[/math] is the Primorial.

 

In other words, [math]x[/math] is prime if [math]x[/math] and the product of all primes smaller than x are coprime, or relatively prime.

 

While this could be used to prove a numbers primality, I think it'd be inefficient, if only because one would have to know all the primes smaller than x. It is possible to use a normal factorial in place of the primorial, however, regardless of the vast increase in the size of the resulting number, there are much faster methods out there.

What I was think however is if one used this to generate primes. While the number that one would deal with would be huge, and get bigger and bigger with each new prime, it's only one number. The algorithm is I think pretty fast (I could only write an implementation in C++ using built in datatypes, which means I didn't get farther than 33 before I encountered overflows), because we only have to find the GCD of two numbers, and since we would only have to remember one number (that being the primorial) the memory requirements wouldn't be that horrible...yes, it's a big number, but I'm hoping it still requires less memory than standard approaches do.

 

However, I'm only 16, and so have no idea how to find out this method's computation complexity, nor do I have any idea about the amount memory that's required. Wikipedia states something regarding the latter when you look at the primorial page, but that really doesn't tell me anything, if only because I still don't understand little-o notation (or big-O for that matter).

 

I know I'm missing something here, since if it'd be as simple as I put it, this algorithm would already be in use...which is why I ask, can someone explain what I'm missing (and dumb it down so a 16 year old can understand)?

 

Thanks in advance,

 

Gabe

[Dave]

I'm really not sure just how useful this would be - what about when you start trying to find primes with only a few hundred digits? The factorial at this point will be absolutely enormous. Finding primes with a few thousand digits would likely prove computationally inefficient.

[Shadow]

I'm aware of that fact. What I'm sort of counting on is the fact that I read that the memory requirements of the Sieve of Atkins (which is, I believe, the fastest known algorithm) are also enormous...and if the supercomputers of this age can store that many numbers, one humongous number shouldn't be a problem...but that's just me and my theories

[Aeternus]

If you look at http://en.wikipedia.org/wiki/Factorial#Rate_of_growth , you'll see that for bigger [math]n[/math], [math]n![/math] has at least [math]n (\log(n) -1)[/math] digits, which means that for a prime with thousands of digits, you are talking of not thousands of digits but of the order of [math]n\log(n)[/math] digits where [math]n[/math] is thousands of digits itself.

 

I.e, you are talking at least [math]O(n \log(n))[/math] space complexity as far as I can see, which is worse than that for Sieve of Atkin given at http://en.wikipedia.org/wiki/Sieve_of_Atkin#Computational_complexity , i.e [math]O(n^{\frac{1}{2} + O(1)})[/math] (presumably the constant in the exponent is very small, as it is supposedly better than the Sieve of Eratothenes, although either way, the space complexity can't be worse than the time complexity) although I don't know the constants involved (See http://en.wikipedia.org/wiki/Big_O_notation for a better idea of O notation. If you make another thread of anything you don't understand, people can explain ).

 

Also, you have to look at the time it takes to calculate a factorial, remembering that multiplication is not a constant time operation. If you look at http://en.wikipedia.org/wiki/Factorial#Computation you'll see that to calculate [math]n![/math] is far worse time complexity than that used for Sieve of Atkins (See http://en.wikipedia.org/wiki/Sieve_of_Atkin#Computational_complexity again).

 

If you look at the time and space complexities for Sieve of Eratothenes (one of the most well known and oldest algorithms for calculating all prime numbers up to a number), I believe your algorithm would still be worse.

 

I'm not sure here whether you are suggesting calculating factorials or primorials for each prime test and going through them, but again this is far worse than simply using the sieves or just going through the list of numbers with individual primality tests. If your algorithm only tests whether a single number is prime, and does not find all prime numbers less than that number, then there are MUCH faster algorithms for testing individual primality without calculating all primes - See http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests .

 

I might be misunderstanding what you are suggesting. If so, could you please explain what I'm misunderstanding.

[Shadow]

Well, you sort of half understood and half misunderstood, but before I get into that, let me thank you for your thorough answer. It's much appreciated.

 

Yes, while the factorial has that growth of digits, don't forget we're talking about the primorial, which, if I understood correctly, grows according to

 

[math]exp([1 + o(1)] n \log(n))[/math]

 

Unfortunately, while I have a very vague idea of what o() is regarding functions (it's basically supposed to mean that one function grows much faster than the other, or that the limit of the two functions as they approach infinity is 0), I have no idea what o(1) means...which means I don't know what 1 + o(1) is So, I don't know if it's more or less, however logically it must be less than the factorial. As for comparing it with the Sieve of Atkin, I have absolutely no idea whether or not [math]exp([1 + o(1)] n \log(n))[/math] is bigger than whatever the Sieve of Atking uses. However, don't forget we only have to remember one single number, not a series. Just one huge number, and that's where I hope the strength of this algorithm (if there is any) lies.

 

As for the time to calculate the Primorial, this is where you get me wrong. I don't intend this to be a method to prove primality, I intend it to be a way of generating primes. And since you generate the primorial on the run, you don't have to worry about time. Let me explain this on an example:

 

 

Let us declare a variable [math]p[/math] that will hold the primorial, and a variable [math]x[/math] that will be the current numbers tested.

 

You start out with two (let's just hard code it to make things simpler). So now we have [math]p = 2[/math] and [math]x = 3[/math]. [math]GCD(2, 3) = 1[/math] which means x is a prime. We update the primorial, that is [math] p = px = 6[/math]. And we move on.

 

[math]x = 4, GCD(4, 6) = 2[/math] x is NOT prime.

[math]x = 5, GCD(5, 6) = 1[/math] x is prime, [math] p = px = 30[/math].

[math]x = 6, GCD(30, 6) = 6[/math] x is NOT prime.

[math]x = 7, GCD(30, 7) = 1[/math] x is prime, [math] p = px = 210[/math].

 

And on and on and on.

 

I don't know if this changes anything, but at least you now have a fuller understanding of what I mean (I hope ).

 

Cheers,

 

Gabe

[the tree]

Try not confuse Big O's with Little O's, they mean very different things.

 

In case their was any confusion: [math]n^{\frac{1}{2} + O(1)} < n \log(n)[/math] for all [math]n[/math] (where [math]\frac{1}{2}+O(1)[/math] is a constant [math]>\frac{1}{2}[/math]).

[Aeternus]

Well, you sort of half understood and half misunderstood, but before I get into that, let me thank you for your thorough answer. It's much appreciated.

 

Yes, while the factorial has that growth of digits, don't forget we're talking about the primorial, which, if I understood correctly, grows according to

 

[math]exp([1 + o(1)] n \log(n))[/math]

 

Unfortunately, while I have a very vague idea of what o() is regarding functions (it's basically supposed to mean that one function grows much faster than the other, or that the limit of the two functions as they approach infinity is 0), I have no idea what o(1) means...which means I don't know what 1 + o(1) is So, I don't know if it's more or less, however logically it must be less than the factorial. As for comparing it with the Sieve of Atkin, I have absolutely no idea whether or not [math]exp([1 + o(1)] n \log(n))[/math] is bigger than whatever the Sieve of Atking uses. However, don't forget we only have to remember one single number, not a series. Just one huge number, and that's where I hope the strength of this algorithm (if there is any) lies.

 

As for the time to calculate the Primorial, this is where you get me wrong. I don't intend this to be a method to prove primality, I intend it to be a way of generating primes. And since you generate the primorial on the run, you don't have to worry about time. Let me explain this on an example:

 

 

Let us declare a variable [math]p[/math] that will hold the primorial, and a variable [math]x[/math] that will be the current numbers tested.

 

You start out with two (let's just hard code it to make things simpler). So now we have [math]p = 2[/math] and [math]x = 3[/math]. [math]GCD(2, 3) = 1[/math] which means x is a prime. We update the primorial, that is [math] p = px = 6[/math]. And we move on.

 

[math]x = 4, GCD(4, 6) = 2[/math] x is NOT prime.

[math]x = 5, GCD(5, 6) = 1[/math] x is prime, [math] p = px = 30[/math].

[math]x = 6, GCD(30, 6) = 6[/math] x is NOT prime.

[math]x = 7, GCD(30, 7) = 1[/math] x is prime, [math] p = px = 210[/math].

 

And on and on and on.

 

I don't know if this changes anything, but at least you now have a fuller understanding of what I mean (I hope ).

 

Cheers,

 

Gabe

 

 

Note here that [math]n\sharp[/math] is not the same as [math]P_n\sharp[/math] and I imagine you should be considering [math]n\sharp[/math] if you are looking at all the primes up to [math]n[/math], which will be much better for you. However, even with this improvement, this still gives a space complexity of [math]O(n)[/math] (from the wiki), which is still worse than Sieve of Atkins.

 

Note here, that whatever your space complexity, your time complexity must be at least that (since you need to write to that many memory locations). You still need to worry about time, since the time to calculate just the final primorial (i.e over the course of the entire algorithm) is too big.

 

Even if your algorithm wasn't already worse time and space complexity (baring in mind, this is just from calculating that one number, I'm not assuming anything other than the calculation of one primorial), there is also the fact that you still need to calculate the GCD for these huge numbers, which in of itself has quite a bad time complexity from what I know, see http://en.wikipedia.org/wiki/Euclidean_algorithm#Running_time . I imagine there are faster algorithms but from what I gather they are not much faster, and they would have to be at least O(log(n)) (afaik) as you'll need to read the numbers (assuming we are considering [math]n[/math] as the number and not the size of the number - this is something one should be careful of, as various resources approach this differently, and considering it in the size of the number throughout would probably be more appropriate).

 

If you are genuinely serious about trying to understand this, then I'd honestly suggest you read up on Big O etc, and work through things, rather than hand waving with "one huge number has to be better than lots of smaller numbers", which just doesn't seem to be true. If I've made some mistakes, please point them out.

Edited October 19, 2008 by Aeternus

[Shadow]

one huge number has to be better than lots of smaller numbers

 

Well yes, that was exactly what I was thinking I'm thinking more and more that know what O and o is would help me a lot. But I thank all of you for your help )

 

Cheers,

 

Gabe