11
$\begingroup$

The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost of primality testing) using a naive algorithm. Is it possible to do it in linear time?

  • 0
    If they're very small can't you just use a sieve?2010-11-11

4 Answers 4

4

You can find the first n primes in time $n\log n/\log\log n$ with the Atkin-Bernstein sieve. This is better than your naive $n\log^5n$ or so algorithm (or drop the exponent by 1 using pretesting with M-R), but still superlinear.

  • 0
    It's worth noting that at least half of your numbers need to be at least prime(n/2), and so the space you need to output the numbers in binary is $\Omega(n\log n)$. So getting the answer in linear time -- or indeed in o(n log n) time -- requires accepting results in a more compact format.2011-04-25
1

Check out Chapter 1 of Paul Pollack's book "Not Always Buried Deep". He lists several elementary proofs for the infinitude of primes, some of which can be adapted to form simple iterative algorithms.

(Sorry, I can't get Latex to work here. Isn't it like MathOverflow? Anyway..)

Let S = {p1...pk} be the set of previously generated coprime integers.

And take M = product of integers in S

Now do any of the following to get new integer coprime to the set S.

  1. (Euclid): M + 1
  2. (Stieltjes): Factor M as A.B in some way, and take A + B
  3. (Euler) Totient(M)
  4. (Braun and Metrod): N = M/p1 + ... + M/p_k
  5. (Goldbach): N = 2 + M

There is also Saidak's proof from the same book:

  • Take N1=n; N2 = N1(N1+1); N3 = N2(N2+1)... Nk=Nk(Nk+1) and so on. This a relative prime sequence.

I am probably missing a couple of other proofs. Anyway, check the book!

EDIT1 : **I am going to retain the answer despite the negative votes, in the hope that it might spur someone else to invent a better algorithm ! *

  • 0
    The proof attributed to Saidak is much older and is expressed more much more concisely in the form $\rm\: n^2\!+n\:$ has a larger set of prime factors than $\rm\:n,\:$ see my [answer here.](http://math.stackexchange.com/a/30133/242)2012-11-06
0

See this "Generating All Co-Prime Pairs".

Method claims to be complete and yield no repeats. Each result generates THREE new children; just stop the generation if either member of the (m, n) pair exceed your definition of "small".

Since this is a declarative generation, that meets your criterion for "linear time", right?

To my (non-mathematician) eyes, this relationship looks a lot like generating Pythagorean-triples.

  • 2
    This g$e$nerates pairs of relatively prime integers, but you can't combine the pairs to make n pairwise relatively prime integers. For example, starting from (3, 1) the metho$d$ makes (5, 3), (7, 3), and (5, 1) in the first step, but these eight numbers are not distinct. Worse, the next step includes (9, 5); while 9 is relatively prime to 5 it is not relatively prime to 3 which appeared earlier. So that method doesn't work here.2012-03-16
-3

I assume S need not be prime (just relatively prime)

For S= {2, 15}

Goldbach method : N = 2 + M

                = 2 + 30                  = 32 (not relatively prime with 2)