Prime power list

Question

Update

Is there any better way of generating the nth prime power?

Chip Hurst gave a great solution for a list below, so

PrimePowersUpTo[x_] := Union @@ Table[Prime[Range[PrimePi[x^(1/n)]]]^n, {n, Log2[x]}]
pp=PrimePowersUpTo[10^7];
pp[[n]]

would work, but I was wondering whether there was a more direct way?

Original question

I am trying to get a list of prime powers, but I can only seem to get one that goesx to 10^7.

xmax = 10000000;
rr = DeleteCases[Table[If[PrimePowerQ[n] == True, n, 0], {n, 1, xmax}], 0];

or

Select[Range[10], PrimePowerQ]

I tried using Artes' idea of taking log base prime as per here, but didn't get very far.

Is there any way I can go to 10^12?

Answer 1

Here's my way of finding the nth prime power. I do a binary search. Unfortunately it's slow for large inputs.

lower[_] = 2;
upper[x_] := Prime[x]

PrimePower[n_] := Module[{lo = lower[n], hi = upper[n], mid, pp},
    mid = Quotient[lo + hi, 2];

    While[lo < mid < hi && (pp = PrimePowerPi[mid]) != n,
        If[pp > n,
            hi = mid,
            lo = mid
        ];
        mid = Quotient[lo + hi, 2];
    ];

    PreviousPrimePower[mid]
]

PreviousPrimePower[x_] := Max[Table[NextPrime[x^(1/n), -1]^n, {n, Log2[x]}]]

Examples:

PrimePowerPi[10^7]

665134

PrimePower[665134]

9999991

PrimePowerPi[10^12]

37607992088

PrimePower[37607992088]

999999999989

---

From Daniel Lichtblau:

Feel free to use this variant (divides more finely).

PrimePowerb[n_] := Module[
  {lo = lower[n], hi = upper[n], mid, ppmid, pphi, pplo}, 
  mid = Round[.95*hi];
  ppmid = PrimePowerPi[mid];
  pplo = 1;
  pphi = PrimePowerPi[hi];
  While[lo < mid < hi && ppmid != n,
   If[ppmid > n,
    hi = mid;
    pphi = ppmid;
    mid = mid + Round[(lo - mid)*(n - ppmid)/(pplo - ppmid)];
    ,
    lo = mid;
    pplo = ppmid;
    mid = mid + Round[(hi - mid)*(n - ppmid)/(pphi - ppmid)];
    ];
   If[mid == lo, mid++];
   If[mid == hi, mid--];
   ppmid = PrimePowerPi[mid];
   ];
  PreviousPrimePower[mid]]

Answer 2

How about

PrimePowersUpTo[x_] := Union @@ Table[Prime[Range[PrimePi[x^(1/n)]]]^n, {n, Log2[x]}]

PrimePowersUpTo[10^7] // Length

665134

Now about getting the first 10^12 prime powers. You would want to get them in batches (segmented sieve) because there are about 38 billion of them:

PrimePowerPi[x_] := Sum[PrimePi[x^(1/n)], {n, Log2[x]}]

PrimePowerPi[10^12]

37607992088