2
$\begingroup$

Some very good algorithms exist to generate all primes $p$ up to some bound $N$, like the sieve of Erastothenes and the sieve of Atkin. However, suppose I want to generate a (sorted) list of all prime powers $p^n \leq N$ rather than just the primes themselves.

A very intuitive approach is to generate all primes $p \leq N$ and then take $p, p^2, \dots, p^{\lfloor\log_p(n)\rfloor}$, put it all in one big list and then sort it. This can easily be optimized somewhat by multiplying the previous power $p^i$ by $p$ to obtain the next one: $p^{i+1} = p^i \cdot p$; rather than calculating every power separately.

I would assume there are faster ways of generating such a list, but I haven't really found anything in literature (so far). I'm not at home in this field, though, so I may just be looking in the wrong places.

A few ideas I've been toying with are:

  • Maybe one can modify a prime sieve to also identify prime powers?
  • Similarly, maybe one can modify a good algorithm that identifies perfect powers to identify prime powers instead, and then sieve through all integers $\leq N$.

So, the question is: does anyone know any algorithms to generate the prime powers, is there any literature about this to be found, or can you come up with something yourself?

$\endgroup$
1
$\begingroup$

What you are looking for is numbers between $2$ and $N$ that are divisible by only one prime number. So you should do an Erathosten's sieve with three colors (white, grey, black).

Basically, you begin with the list $L:=[2,\dots,N]$ all colored in white. Now you do the same thing as in the Erathosten sieve. If the white cases still correspond to prime numbers, you will have two kinds of colored cases.

The grey cases which have only been colored once (those are the prime powers which are not prime) and the black cases (which have been colored at least twice).

You finally end up with prime numbers (in white), prime powers but not prime (in grey) and non-prime powers (in black).

Example : when $N=10$. We begin with $L=[2,...,10]$ and all elements colored in white.

-first step : $2$ is white, we color in $L$ every $2$ numbers beginning at $2$, that is $4$, $6$, $8$ and $10$ are colored once (in grey).

-second step : the first white number after $2$ is $3$. We color every $3$ numbers in $L$ beginning at $3$, that is $6$ (which has already been colored in grey so is colored in black) and $9$ in grey.

-third step : the first white number after $3$ is $5$. We color every $5$ numbers in $L$ beginning at $5$, that is $10$ (which has already been colored once in grey so is colored in black).

-fourth step : the remaining number in white is $7$.

Finally we have $2,3,5,7$ in white, $4,8,9$ in grey and $6,10$ in black.

$\endgroup$
  • 1
    $\begingroup$ I didn't get it. You jump to "The grey cases" without even explaining what "grey" means in this context (well, you say "have only been colored once", but you never mention more than one coloring-operation prior to this statement). I think you should either clarify your suggestion more precisely, or at least add an example (e.g, how do we spot $125$ as a prime power?). $\endgroup$ – barak manos May 15 '16 at 15:56
  • $\begingroup$ @barakmanos, you are right, I will add something about it. $\endgroup$ – Clément Guérin May 15 '16 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.