Na potrzeby tego wyzwania Prime Power of a Prime (PPP) jest zdefiniowany jako liczba, którą można zdefiniować jako liczbę pierwszą do potęgi liczby pierwszej. Na przykład 9 jest PPP, ponieważ można go przedstawić jako 3 ^ 2. 81 z drugiej strony nie jest PPP, ponieważ może być reprezentowane tylko jako 3 ^ 4, a 4 nie jest liczbą pierwszą. Pierwsze kilka PPP to: 4, 8, 9, 25, 27, 32, 49, 121, 125, 128, 169, 243, 289, 343 ... To jest sekwencja OEIS A053810

Twoje zadanie:

Napisz program lub funkcję, która dla liczby całkowitej n zwraca / wyprowadza n-ty PPP, indeksowany 1 lub 0, zależnie od tego, co wolisz.

Wejście:

Liczba całkowita od 0 do 1000, otrzymana dowolną rozsądną metodą.

Wynik:

PPP o indeksie wskazanym przez dane wejściowe.

Przypadki testowe:

Są one indeksowane 1, więc jeśli twój program pobiera dane indeksowane 0, to dla tych danych wejściowych należy uzyskać to samo wyjście - 1.

3  -> 9
6  -> 32
9  -> 125

Punktacja:

Ten golfowy kod , najniższy wynik w bajtach wygrywa!

05AB1E (starsza wersja) ,  9  7 bajtów

Zaoszczędzono 2 bajty dzięki @KevinCruijssen

µNÓ0Kp»

Wypróbuj online!

µ           # while counter_variable != input:
 N          #   push iteration counter                       e.g. 125
  Ó         #   get prime exponents                          -> [0, 0, 3]
   0K       #   filter out zeros                             -> [3]
     p      #   is prime?                                    -> [1]
      »     #   join with newlines: we use » instead of J
            #   so that [0,1] is not interpreted as truthy   -> 1
            #   implicit: if 1, increment counter_variable

Łuska , 10 bajtów

!fȯṗ§*ELpN

Wypróbuj online!

Wyjaśnienie

!fȯṗ§*ELpN  Implicit input.
 f       N  Filter the natural numbers by this function:
  ȯṗ§*ELp    Argument is a number, say 27.
        p    Prime factors: [3,3,3]
       L     Length: 3
      E      Are all elements equal: 1
    §*       Multiply last two: 3
  ȯṗ         Is it prime? Yes, so 27 is kept.
!           Index into remaining numbers with input.

Właściwie 14 bajtów

Na podstawie rozwiązania Pyth'a pana Xcodera . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;ur♂P;∙⌠iⁿ⌡MSE

Ungolfing

                Implicit input n
;ur             Duplicate and push [0..n]
   ♂P           Push the 0th to nth primes
     ;∙         Push Cartesian square of the primes
       ⌠iⁿ⌡M    Reduce each list in the Cartesian square by exponentiation
            SE  Sort the list and get the nth index (0-indexed)

Mathematica, 48 bajtów

Sort[Join@@Array[(p=Prime)@#^p@#2&,{#,#}]][[#]]&   

Wypróbuj online!

ale Martin Ender miał lepszy pomysł i oszczędził 6 bajtów

Mathematica, 42 bajty

Sort[Power@@@Prime@Range@#~Tuples~2][[#]]&   

Wypróbuj online!

Galaretka , 12 11 10 bajtów

1 bajt dzięki Dennisowi.

ÆN€*þ`FṢị@

Wypróbuj online!

R + liczby, 57 bajtów

function(n,x=numbers::Primes(2*n))sort(outer(x,x,"^"))[n]

Wypróbuj online!

outer jest taką przydatną funkcją.

Dość pewne, że to zawsze zadziała. Zrobię formalny argument, kiedy będę miał czas.

Haskell , 95 85 80 bajtów

-10 bajtów dzięki @Lynn
-5 bajtów dzięki @WillNess

W oparciu o 0

(!!)[x|x<-[2..],p<-[[i|i<-[2..x],all((>)2.gcd i)[2..i-1]]],or[y^e==x|e<-p,y<-p]]

Wypróbuj online!

Wyjaśnienie

(!!)                    -- point-free expression, partially evaluate index-access operator
[x|x<-[2..]             -- consider all integers x>=2
,p<-                    -- let p be the list of all primes <=x
[[                      -- list of a list so p ends up as a list
i|i<-[2..x],            -- consider all i<=x to be potentially prime
all((>)2.gcd i)[2..i-1] -- if the gcd of i with all smaller integers is
                        -- smaller than 2 then this i is actually prime
 ]],or                  -- if any of the following list entries is true
[y^e==x|                -- the condition y^e==x holds for x with ...
e<-p,y<-p]              -- y and e being prime, i.e. x is a PPP,
]                       -- then add this x to the output sequence / list

Python 2 , 163 157 137 136 136 bajtów

• Zaoszczędzono sześć bajtów, używając input()zamiast definiować funkcję.
• Oszczędność czterech bajtów dzięki Felipe Nardi Batista ; łączenie dwóch pętli.
• Oszczędność szesnastu bajtów dzięki tylko ASCII .
• Oszczędność bajtu dzięki ArBo .

p=input();r=i=0;e=lambda p:all(p%d for d in range(2,p))
while~-i<p:
 r+=1
 for x in range(r*r):y=x%r;x/=r;i+=x**y==r>e(x)>0<e(y)
print r

Wypróbuj online!

Pyth , 15 bajtów

e.f/^FR^fP_TSZ2

Wypróbuj tutaj! lub Zweryfikuj więcej przypadków testowych.

Wyjaśnienie

ef / ^ FR ^ fP_TSZ2 - Pełny program. Q oznacza wkład.

 .f - Pierwsze wyniki Q z prawdziwymi wynikami. Używa zmiennej Z.
        fP_TSZ - Filtruj zakres [1, Z] dla liczb pierwszych.
       ^ 2 - kwadrat kartezjański. Zasadniczo produkt kartezjański z samym sobą.
    ^ FR - Zmniejsz każdą listę przez potęgowanie.
  / - Policz wystąpienia Z w ^.
e - ostatni element.

JavaScript 137 133 bajtów

P=n=>{for(p=[i=2];j=++i<n*9;j^i&&p.push(i))
for(;j*j<=i;)j=i%++j?j:i
x=[]
for(i of p)
for(j of p)
x[i**j]=1
return Object.keys(x)[n]}

console.log(P(1000))
console.log(P(800))
console.log(P(9))
console.log(P(5))

** normalny algorytm (wynik 100 ms) P = n => {

  for(p=[i=2];f=++i<=n*10;!f||p.push(i))
    for(j=0;f&&(x=p[j++])*x<=i;)
      f=i%x
  x=[]
  T=0
  for(i of p)
  for(j of p)
  {
    l= i**j
    if(++T>n &&x.length<l )
    break
    x[l] = 1
  }
  return Object.keys(x)[n]
}

APL (Dyalog Extended) , 15 bajtów

{⍵⌷∧∊∘.*⍨¯2⍭⍳⍵}

Wypróbuj online!

Wyjaśnienie

{⍵⌷∧∊∘.*⍨¯2⍭⍳⍵}

              ⍵   Right argument. Our input.
{              }  Wraps the function in dfn syntax which allows us to use ⍵.
             ⍳     Range [1..⍵].
          ¯2⍭     Get the n-th prime for each n in the range.
      ∘.*⍨        Get the prime powers of each prime.
     ∊            Flatten the list.
    ∧             In Extended, this is monadic sort ascending.
 ⍵⌷               Get the input-th index of the list of prime powers of primes.

Perl 6 , 50 bajtów

{(sort [X**] (^7028,^24)>>.grep(&is-prime))[$_-1]}

Wypróbuj online!

  (^7028,^24)            # create 2 ranges from 0
     >>.grep(&is-prime)  # grep for primes in both
 [X**] ...               # calc each exponential pair (2^2, 2^3, 2^5...)
(sort ... )[$_-1]        # sort and get value at index n-1

Powodem 24 i 7028 jest to, że największa wartość (n = 1000) to 49378729, czyli 7027 ^ 2, a największa moc podstawowa 2, która do tego pasuje, wynosi 23. Tak więc obejmując 2..7027 ^ 2 .. 23 obejmuje wszystkie elementy z pierwszych 1000 (i wiele części zamiennych).

Pyth - 13 bajtów

e.f&P_lPZ!t{P

Pakiet testowy .

PARI / GP, 48 bajtów

f(n)=[x|x<-[1..4^n],isprime(isprimepower(x))][n]

Jeśli nie policzysz f(n)=części, to 43 bajtów.

Inne podejście bez zestawu notacji, które nie sprawdza tylu niepotrzebnych przypadków:

f(n)=c=0;i=1;while(c<n,i++;isprime(isprimepower(i))&&c++);i

Java 8, 211 bajtów

import java.util.*;n->{List l=new Stack();for(int a=2,b;a<132;a++)for(b=2;b<132;b++)if(p(a)*p(b)>0)l.add(Math.pow(a,b));Collections.sort(l);return l.get(n);}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

Bardzo nieefektywna metoda. Zasadniczo oblicza wszystkie PPP od 2 ² do 999 ⁹⁹⁹ 132 ¹³² i zapisuje je na liście, następnie sortuje tę listę, a następnie pobiera nz listy tę pozycję.

EDYCJA: Zamiast używać 999 ^999, co daje listę 28.225 pozycji, teraz używam 132 ^132, co daje listę tylko 1024 pozycji. To nieco poprawia wydajność i jest całkowicie do przyjęcia, ponieważ w wyzwaniu stwierdza się, że powinniśmy wspierać dane wejściowe od indeksu 0 do 1000. (Zmiana 1e3na 132nie wpływa jednak na liczbę bajtów.)

Wyjaśnienie:

Wypróbuj tutaj.

import java.util.*;           // Required import for List, Stack and Collections

n->{                          // Method with integer as parameter and Object as return-type
  List l=new Stack();         //  List to store the PPPs in
  for(int a=2,b;a<132;a++)    //  Loop (1) from 2 to 1,000 (exclusive)
    for(b=2;b<132;b++)        //   Inner loop (2) from 2 to 1,000 (exclusive)
      if(p(a)*p(b)>0)         //    If both `a` and `b` are primes:
        l.add(Math.pow(a,b)); //     Add the power of those two to the List
                              //   End of loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  Collections.sort(l);        //  Sort the filled List
  return l.get(n);            //  Return the `n`'th item of the sorted List of PPPs
}                             // End of method

int p(int n){                 // Separated method with integer as parameter and return-type
  for(int i=2;                //  Index integer (starting at 2)
      i<n;                    //  Loop from 2 to `n` (exclusive)
    n=n%i++<1?                //   If `n` is divisible by `i`:
       0                      //    Change `n` to 0
      :                       //   Else:
       n                      //    Leave `n` the same
  );                          //  End of loop
  return n;                   //  Return `n` (which is now 0 if it wasn't a prime)
}                             // End of separated method

J, 21 bajtów

{[:/:~@,[:^/~p:@i.@>:

Zerowa indeksowana funkcja anonimowa.

Wypróbuj online!

Próbuję wrócić do kołysania rzeczy, ale wydaje mi się, że zapomniałem wszystkich sztuczek, aby stworzyć dobre monadyczne łańcuchy.

Krótkie wyjaśnienie

Tworzy tabelę liczb pierwszych od 0-tej liczby pierwszej do liczby pierwszej na podstawie indeksu wejścia plus 1 (w celu uwzględnienia 0). Spłaszcza tę listę, sortuje ją, a następnie indeksuje. Zdaję sobie teraz sprawę, że może to dawać niepoprawne wyniki dla niektórych wartości, ponieważ tabela może być niewystarczająco duża - w takim przypadku edytowałbym na stałe wartość 1E4, która powinna wystarczyć. Nie mogę tego udowodnić w ten czy inny sposób (to pasuje do podanych przypadków testowych), więc daj mi znać, jeśli to jest problem.

Również 21 bajtów

3 :'y{/:~,^/~p:i.>:y'