Method for generating prime numbers

Post Reply New Topic

Sorry, I was on completely the wrong track then.

So what is your reading of the claim then? Something like, "Task (1.) is at least as hard as Task (2.), where the tasks are:
(1.) Find all primes from 1 to N.
(2.) Find out which primes go into N, given that you already know all the primes less than N."

This might be true, but how is it in the spirit of the original claim? It seems a bit arbitrary.

... and how would you do this?

No.

The only better than AKS which we know are probabilistic algorithms (which have their own problems).

If all prime numbers beside 2 and 3 can still be expressed that way though, could one not use that in combination with the Sieve of Eratosthenes to speed up the algorithm?

Okay, yes, you are right. Some people think they are random, but they obviously are not mathematicians!

I still think there should be some explicit formula to determine them, although the formula may be too complex to meaningful.

I did some further reading on Ramanujan today and the guy is absolutely brilliant. I wish I had his mind.

Can you prove this? (note: we're talking about finding all of them from 2 to n here, not just one number)


That there is no significant shortcut to finding all the primes. If you want them all (up to n) then you have to start at the bottom and build up, and any other method will give up on certainty, or give up on getting them all, or end up doing at least as much work.

I don't have a proof of it, but I think it seems likely.


From what I've been reading, it seems like something along these lines is standard practice. What I've read is a bit more complicated, it uses 30 (2*3*5), and adds 1, 7, 11, 13, 17, 19, 23, or 29 instead of 6 and 1 or 5.

The following Maple code finds all primes using isprime, which is a probabilistic algorithm.



In just a minute it has checked all <=13254203, which are exactly 864711 primes.

The complexity to get all primes <=n with this approach is O(n) calls to isprime, if isprime was AKS we would had O(n*log(n)^6), with Miller-Rabin (I assume that Maple use this) O(n*log(n)^2).
If isprime is simply check divisibility by all the previous n-1 numbers we would get O(n^2), if we only check up to sqrt(n) then O(n*sqrt(n))=O(n^(3/2)).
If we try to use the primes we have already calculated, dividing by them instead of dividing by all numbers, we would be diving by all primes <= than sqrt(n). Here appears the Prime-counting function pi(k)~k/ln(k), hence we would be checking divisibility by O(pi(sqrt(n)))=O(sqrt(n)/ln(sqrt(n)))=O(n^(1/2)/log n) for each number. Giving the total complexity of O(n^(3/2)/log n).
Since n^(1/2)/log n > log(n)^6 (for enough large n) we have that using AKS is better than simply dividing by the previous primes we have found.

With a Sieve of Eratosthenes approach we would get a block of n numbers (hence spatial complexity O(n), but that is another matter)
and then apply sieves.
The sieve by p requires looking O(n/p) ~ O(n) (as we use primes p<=sqrt(n)<<n).
We have a sieve for each prime p<=sqrt(n), this is pi(sqrt(n)) \in O(n^(1/2)/log n)
Again we have O(n^(3/2)/log n).

No. This is akin to the halting problem or the busy beaver, a non-computable function.



The Sieve of Atkin is an optimized version. However, I have not been able to implement it in a manner that makes it faster than Sieve of Eratosthenes. On a boolean array in Java, Eratosthenes runs 2 billion in 38 seconds, 44 with a BitSet instead. Atkin runs slower. It does a number of wasteful calculations I haven't figured out how to ace faster.
If anyone knows how to bring down its running time (I heard it can be REALLY fast), please do share that knowledge.



I'm sure more than one mathematician lost their minds over this.

But now it's back to the vague form in which it started. I can't make any rigorous sense out of this statement.



Put it this way. If you did have a proof, what would the theorem be?

This isn't wrong, since O() is an upper limit, but according to a couple of papers I've found, the Sieve of Eratosthenes runs in O(n) or O(n log log n). (I think the difference is a matter of an optimization being made or not.)

The Sieve of Atkin runs in O(n/log log n). So both of them are a bit faster than using AKS on every number less than n, but the small amount of difference surprised me.


If we had the best single prime checker (call its running time s) and the best sieve prime checker (call its running time m), then for creating a list of all primes < n, m=O(s). In other words, they might be asymptotically the same, or s might be asymptotically slower.

I have done in Maple the following implementation of the Sieve, for the same size that I got with my previous approach in 1 minute:

And I got "Tiem elapsed", 47.338.

So at least for small numbers the sieve is actually faster as you said.
Seems I had something wrong in my reasoning, the O(n/p) ~ O(n) is be a little brute. They can be added correctly using Prime_harmonic_series

As a person with a background in computer programming, I am definitely interested in formulas for speeding up calculation in prime calculation.

However, I guess I am more drawn to pure math. Efficient algorithms and recursive algorithms are very important and practical, but they are not quite what I am looking for.

What do you think of this quote?
n a 1975 lecture, D. Zagier commented "There are two facts about
the distribution of prime numbers of which I hope to convince you so
overwhelmingly that they will be permanently engraved in your
hearts. The first is that, despite their simple definition and role
as the building blocks of the natural numbers, the prime numbers
grow like weeds among the natural numbers, seeming to obey no other
law than that of chance, and nobody can predict where the next one
will sprout.

The second fact is even more astonishing, for it states just the
opposite: that the prime numbers exhibit stunning regularity, that
there are laws governing their behavior, and that they obey these
laws with almost military precision" (Havil 2003, p. 171).

Confirms my suspicions.

I would love to see a proof that there is no formula for generating primes that does not rely on recursion. I most likely would not understand it but I would still be interested in seeing it if anyone know of one.

I'm not a high level mathematician but I am fascinated by this stuff. Anyone have further insight?

I'm still confused about how to make sense out of your terminology "single prime checker" and "sieve prime checker".

If a "single prime checker" does this:

And a "sieve prime checker" does this:

Then you are claiming that running a single prime checker on every number from 1 to M will never be faster than running a sieve prime checker on M? Well of course not! The sieve prime checker is more specialised. Or is there some sense of the word "sieve" that means that it can apply to some algorithms of type (2.) and not others?

There is a method for generating all primes from 1 to N that does not rely on recursion. It's just the obvious one. Go through each number from 1 to N, and for each number, check whether any number lower than it goes into it.

Okay, well, I consider that an algorithm.

I guess I was not clear with my wording.

Recursion was the wrong word to use.

I was referring to something more along these lines of Euler's equation, namely n^2 + n + 41, which gives all the primes form n= 0 to 39.

An interesting formula, but clearly artifical since it fails for n>=40. I guess I would like to see a proof that no finite equation is satisfactory. Intuitively, this actually seems to be pretty obvious, but proving it would be difficult I would think.

Ah okay, so you are speculating that there is no "nice" equation involving a variable n such that the equation is true if and only if n is prime?

It is difficult to prove things like that, because the word "nice" isn't actually such a simple concept. I guess it means "able to be written as a finite amount of multiplication, addition, exponentation, infinite sums, infinite products, etc. etc."

EDIT: look here, some results on this sort of thing are known:
http://en.wikipedia.org/wiki/Formula_for_primes

Last edited by Declension on 21 Feb 2012, 4:42 am, edited 1 time in total.