Una potencia prima es un número entero positivo n que se puede escribir en la forma n = p ^k donde p es un número primo yk es un número entero positivo. Por ejemplo, algunas potencias principales son [2, 3, 5, 4, 9, 25, 8, 27, 125].

A continuación, considere los poderes primarios de 2. Estos son [2, 4, 8, 16, ...]y pueden escribirse en la forma 2 ^k . Todos se incluirían al considerar las potencias principales por debajo de 20. Sin embargo, 16 es la potencia principal máxima con una base de 2 en ese rango. Una potencia primaria p ^k es máxima en un rango si es la potencia más alta de p en ese rango. Solo estamos interesados ​​en la potencia primaria máxima en cada rango, por lo que todas las potencias primarias inferiores deben excluirse.

Su objetivo es escribir una función o programa que tome un número entero positivo n y produzca las potencias máximas máximas en el rango [2, 3, 4, ..., n].

Gracias a @ Peter Taylor por aclarar la definición de potencia máxima máxima y más.

Reglas

• Este es el código de golf, así que haga su código lo más corto posible.
• Las potencias máximas máximas se pueden emitir en cualquier orden, pero no debe haber duplicados.

Casos de prueba

n      result
1      []
2      [2]
3      [2, 3]
4      [3, 4]
5      [3, 4, 5]
6      [3, 4, 5]
7      [3, 4, 5, 7]
20     [5, 7, 9, 11, 13, 16, 17, 19]
50     [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100    [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000  <1229 results>
       [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

La lista completa de potencias máximas máximas para 10000 se puede encontrar aquí .

Jalea , 7 4 bytes

æḟÆR

Pruébalo en línea!

Cómo funciona

æḟÆR  Main link. Argument: n

  ÆR  Prime range; yield all primes in [1, ..., n].
æḟ    Power floor; round n down to the nearest power of each prime in the range.

Mathematica, 44 43 40 bytes

Guardado 4 bytes gracias a millas y Martin Ender

n#^⌊#~Log~n⌋&/@Select[Range@n,PrimeQ]

(x=Prime@Range@PrimePi@#)^⌊x~Log~#⌋&

⌊y ⌋son los 3caracteres de bytes U+230Ay U+230Brepresentan \[LeftFloor]y \[RightFloor], respectivamente.

Explicación:

Pura función. #es la abreviatura de lo Slot[1]que representa el primer argumento de la Function. PrimePi@#cuenta el número de primos menor o igual a #, Range@PrimePi@#es la lista de los primeros PrimePi[#]enteros positivos, y también lo Prime@Range@PrimePi@#es la lista de primos menor o igual a #(este es un byte más corto que Select[Range@#,PrimeQ]). El símbolo xes Setigual a esta lista, entonces elevado a la Power ⌊x~Log~#⌋, que es la lista de Floor[Log[n,#]]para cada nen x. En Mathematica, elevar una lista a Powerotra lista de la misma longitud da como resultado la lista de las potencias de sus elementos correspondientes.

MATL, 13 bytes

ZqG:!^tG>~*X>

Pruébalo en línea!

Explicación

        % Implicitly grab the input as a number (N)
Zq      % Get an array of all primes below N
G:!     % Create an array from [1...N]
^       % Raise each prime to each power in this array which creates a 2D matrix
        % where the powers of each prime are down the columns
tG>~    % Create a logical matrix that is TRUE where the values are less than N
*       % Perform element-wise multiplication to force values > N to zero
X>      % Compute the maximum value of each column
        % Implicitly display the resulting array

Jalea , 8 bytes

ÆR*ÆE€»/

Pruébalo en línea!

Cómo funciona

ÆR*ÆE€»/  Main link. Argument: n

ÆR        Prime range; yield all primes in [1, ..., n].
   ÆE€    Prime exponents each; yield the exponents of 2, 3, 5, ... of the prime
          factorization of each k in [1, ..., n].
          For example, 28 = 2² × 3⁰ × 5⁰ × 7¹ yields [2, 0, 0, 1].
  *       Exponentiation; raise the elements of the prime range to the powers
          of each of the exponents arrays.
      »/  Reduce the columns by maximum.

Jalea , 12 9 bytes

RÆEz0iṀ$€

Pruébalo en línea! (El método es demasiado lento para el caso 10000).

¿Cómo?

Construye la lista de p ^k en orden de p .

RÆEz0iṀ$€ - Main link: n                      e.g. 7
R         - range(n)                          [1 ,2  ,3    ,4  ,5      ,6    ,7]
 ÆE       - prime factor vector (vectorises)  [[],[1],[0,1],[2],[0,0,1],[1,1],[0,0,0,1]]
   z0     - transpose with filler 0           [[0,1,0,2,0,1,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]]
       $€ - la$t two links as a monad, for €ach       ^             ^                   ^                   ^
     i    -     first index of                        4             3                   5                   7
      Ṁ   -     maximum                       [4,3,5,7]

Pyth, 13 bytes

m^ds.lQdfP_TS

Pruébalo aquí!

        f   S -  filter(v, range(1, input))
         P_T  -   is_prime(T)
m             - map(v, ^)
    .lQd      -    log(input, d)
   s          -   int(^)
 ^d           -  d ** ^

No he jugado con Pyth en mucho tiempo, por lo que agradezco cualquier consejo de golf.

No pude obtener una solución de Mathematica más corta que la solución de ngenisis , pero pensé en ofrecer un par de enfoques alternativos (con suerte interesantes).

Mathematica, 65 bytes

#/#2&@@@({#,#}&/@Range@#~Select~PrimeQ//.{a_,b_}/;a<=#:>{b a,b})&

Primero usamos {#,#}&/@Range@#~Select~PrimeQpara construir una lista de todos los primos en el rango apropiado, pero con pares ordenados de cada primo, como { {2,2}, {3,3}, ...}. Luego, operamos en esa lista repetidamente con la regla de reemplazo {a_,b_}/;a<=#:>{b a,b}, que multiplica el primer elemento del par ordenado por el segundo hasta que el primer elemento excede la entrada. Luego aplicamos #/#2&@@@a la salida, para cada par ordenado, el primer elemento dividido por el segundo. (Terminan ordenados por el primo subyacente: un resultado de ejemplo es {16, 9, 5, 7, 11, 13, 17, 19}).

Mathematica, 44 bytes

Values@Rest@<|MangoldtLambda@#->#&~Array~#|>&

La función de von Mangoldt Λ(n)es una función interesante de teoría de números: es igual a 0 a menos que nsea ​​una potencia primaria p ^k , en cuyo caso es igual log p(no log n). (Estos son registros naturales, pero no importará). Por lo tanto, MangoldtLambda@#->#&~Array~#crea una matriz de reglas { 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }cuya longitud es el entero de entrada.

Luego convertimos esta lista de reglas en una "asociación" usando <|...|>. Esto tiene el efecto de retener solo la última regla con cualquier valor dado a la izquierda. En otras palabras, será tirar Log[2]->2y Log[2]->4y Log[2]->8y mantener sólo Log[2]->16(suponiendo que la entrada se encuentra entre 16 y 31 para este ejemplo). Por lo tanto, los únicos lados derechos restantes son las potencias máximas máximas, a excepción de la única regla restante 0->n, donde nes la potencia no principal más grande hasta el entero de entrada. Pero Restdescarta esa regla no deseada y Valuesextrae el lado derecho de las reglas de la asociación. (Terminan ordenados como anteriormente).

Una versión un poco más larga (46 bytes), que cuenta el número de apariencias de cada uno log py luego expone para convertir a las potencias primarias máximas:

E^(1##)&@@@Rest@Tally[MangoldtLambda~Array~#]&

CJam , 21 20 bytes

Guardado 1 byte gracias a Martin Ender

ri_){mp},f{\1$mLi#}p

Pruébalo en línea!

Explicación

ri                    e# Read an integer from input (let's call it n)
  _                   e# Duplicate it
   ){mp},             e# Push the array of all prime numbers up to and including n
         f{           e# Map the following block to each prime p:
           \          e#   Swap the top two elements of the stack
            1$        e#   Copy the second element down in the stack. Stack is now [p n p]
              mL      e#   Take the base-p logatithm of n
                i     e#   Cast to int (floor)
                 #    e#   Raise p to that power
                  }   e# (end of map block)
                   p  e# Print

Brachylog , 15 bytes

⟧{ḋ=}ˢ⊇Xhᵐ≠∧X×ᵐ

Pruébalo en línea!

Esto genera los poderes de mayor a menor.

Esto es muy ineficiente.

Explicación

⟧                   The Range [Input, Input - 1, ..., 1, 0]
 {  }ˢ              Select:
  ḋ=                  The elements of that range whose prime decompositions are lists of the
                      same element (e.g. [3,3,3]); output is those prime decompositions
      ⊇X            X is an ordered subset of that list of prime decompositions
       Xhᵐ≠         All first elements of the prime decompositions are different (that is,
                      X contains prime decompositions with different primes each times)
           ∧
            X×ᵐ     Output is the result of mapping multiplication to each element of X

Esto encontrará primero las descomposiciones principales más grandes para cada primo debido a la forma en que ⊇funciona: de izquierda a derecha y de subconjuntos más grandes a más pequeños.

Brachylog , 24 21 19 bytes

3 + 2 bytes guardados gracias a Fatalize!

Esta es la primera vez que uso Brachylog, y sé que algunas cosas podrían haberse hecho de manera más corta, pero estoy feliz de que incluso funcione: D

{≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠ

Pruébalo en línea! (Los valores de retorno están ordenados por sus primos base)

Explicación:

{................}ᶠ           #Find all possible results of what's inside.
 ≥.                           #Input is >= than the output.
  .~^ℕ₁ᵐ                      #Output can be calculated as A^B, where A and B are
                              #Natural numbers >=1.
        hṗ                    #The first of those numbers (A) is prime
          :.≜×>?              #That same element (A), multiplied by the output
                              #is greater than the input - This means 
                              #that B is the maximal exponent for A.
                ∧             #No more restrictions on the output.

05AB1E , 15 12 bytes

ƒNpiN¹N.nïm,

Pruébalo en línea!

Explicación

ƒ             # for N in [0 ... input]
 Npi          # if N is prime
    N         # push N
     ¹N.n     # push log_N(input)
         ï    # convert to int
          m   # raise N to this power
           ,  # print

Bash + utilidades GNU, 74 bytes

seq $1|factor|sed "s@.*: \(\w*\)\$@\1;l($1);l(\1);print \"/^p\"@"|bc -l|dc

Pruébalo en línea!

El número de entrada se pasa como argumento. La salida se imprime en stdout. (Como es habitual, se ignora stderr).

Salida de muestra:

./maximalprimepowers 100 2>/dev/null
64
81
25
49
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

./maximalprimepowers 10000 2>/dev/null | wc -l
1229

Así es como funciona:

Llame al argumento N.

seqgenera todos los números del 1 al N y los factorfactoriza a todos.

La expresión regular en la llamada a sed identifica aquellas líneas donde el número es un P principal, y reemplaza esas líneas con líneas que tienen la forma `

P;l(N);l(P);print "/^p"

(donde P y N se reemplazan por sus valores numéricos reales, y todo lo demás se copia literalmente, incluso las comillas y los puntos y comas, y la cadena print).

Estas líneas se alimentan como entrada a bc -l; bc imprime los valores de los tres números indicados, cada uno seguido de una nueva línea, y luego imprime los caracteres /^p. (En bc, l (x) denota el logaritmo natural de x.) JK K

Las cadenas que imprime bc se alimentan como entrada a dc; dc imprime el valor de cada P ^ (log (N) / log (P)) usando aritmética de enteros (truncamiento); esa es la mayor potencia de P que es <= N.

Una cosa que se ha pasado por alto es lo que sucede con las líneas producidas por factores que no corresponden a los números primos. Esas líneas no coinciden con la expresión regular en la llamada a sed, por lo que no se realiza ningún reemplazo en ellas. Como resultado, esas líneas comienzan con un número seguido de dos puntos, lo que genera un error cuando se alimenta como entrada bc. Pero bc simplemente imprime en stderr entonces, lo cual ignoramos; no imprime nada en stdout. Por defecto, stderr se ignora en PPCG .

Haskell , 73 67 66 bytes

p n=[last[x^i|i<-[1..n],x^i<=n]|x<-[2..n],all((>0).mod x)[2..x-1]]

Pruébalo en línea! Uso:

Prelude> p 50
[32,27,25,49,11,13,17,19,23,29,31,37,41,43,47]

Editar: 6 bytes de descuento gracias a Zgarb!

Explicación:

p n=[... x|x<-[2..n]                         ] -- list of all x in the range 2 to n
p n=[... x|x<-[2..n],        mod x<$>[2..x-1]] -- where the remainders of x mod the numbers 2 to x-1
p n=[... x|x<-[2..n],all(>0)$mod x<$>[2..x-1]] -- are all greater 0. This yields all primes in the range.

p n=[    [x^i|i<-[1..n]       ]|...] -- for each of those x generate the list of all x^i with i in the range 1 to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- where x^i is smaller or equal to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- and take the last (that is the largest) element

Jalea , 9 bytes

Ræl/ÆF*/€

Un byte más largo que mi otra respuesta , pero termina con la entrada 10,000 es un par de segundos.

Pruébalo en línea!

Cómo funciona

Ræl/ÆF*/€  Main link. Argument: n

R          Range; yield [1, ..., n].
 æl/       Reduce by least common multiple.
    ÆF     Factor the LCM into [prime, exponent] pairs.
      */€  Reduce each pair by exponentiation.

JavaScript (ES6), 118 120 119 114 112 105 bytes

(n,r)=>(r=k=>[...Array(k-1)].map((_,i)=>i+2),r(n).filter(q=>r(q).every(d=>q%d|!(d%(q/d)*(q/d)%d)&q*d>n)))

Sugerencias bienvenidas. Esto es un poco largo, pero parecía que valía la pena publicarlo porque realiza todas las pruebas de divisibilidad explícitamente en lugar de usar elementos integrados relacionados con números primos.

Notas:

• Un número natural q es una potencia prima <=> todos los divisores de q son potencias del mismo primo <=> para cualquier d que divida q, uno de d y q / d es un divisor del otro.
• Si q es una potencia de p, q es máxima <=> q ​​* p> n <=> q ​​* d> n para cada divisor no trivial d de q.

Sabio, 43 bytes

lambda i:[x^int(ln(i,x))for x in primes(i)]

Asigna cada primo en el rango primes(i)a su potencia máxima máxima. lnes solo un alias de, logpor lo que acepta bases alternativas, aunque su nombre sugiere que solo puede usar base e.

Haskell, 110 90 bytes

s[]=[];s(x:t)=x:s[y|y<-t,y`rem`x>0];f n=[last.fst.span(<=n).scanl1(*)$repeat x|x<-s[2..n]]

--actualizado por los comentarios de Laikoni

Haskell , 70 bytes

f n=[k|k<-[2..n],p:q<-[[d|d<-[2..k],mod k d<1]],k==p*p^length q,p*k>n]

Define una función f. Pruébalo en línea!

Explicación

La idea es filtrar el rango [2..n]para aquellos números kque satisfacen k == p^length(divisors k)y p*k > n, donde pes el divisor primo más pequeño de k.

f n=                -- Define f n as
 [k|                -- the list of numbers k, where
  k<-[2..n],        -- k is drawn from [2..n],
  p:q<-[            -- the list p:q is drawn from
   [d|              -- those lists of numbers d where
    d<-[2..k],      -- d is drawn from [2..k] and
    mod k d<1]      -- d divides k
   ],               -- (so p:q are the divisors of k except 1, and p is the smallest one),
  k==p*p^length q,  -- k equals p to the power of the divisor list's length
                    -- (so it's in particular a prime power), and
  p*k>n]            -- p*k, the next power of p, is not in the range [2..n].

PHP, 101 93 91 88 bytes

solo un poco de matemática real ...

for($n=$argv[$i=1];$n>$j=$i++;$j?:$r[$p=$i**~~log($n,$i)]=$p)for(;$i%$j--;);print_r($r);

Descompostura

for($n=$argv[$i=1];     // loop $i from 2 to $n
    $n>$j=$i++;             // 0.: init $j to $i-1
    $j?:                    // 2. if $i is prime
        $r[$p=$i**~~log($n,$i)]=$p) // 3. add maximum power to results
    for(;$i%$j--;);         // 1. prime check (if $i is prime, $j will be 0)
print_r($r);            // print results

JavaScript ES7, 93 bytes

Recurrir iterativamente idesde 0 hasta e inclusive n. Si ies primo, elevarlo al exponente de piso más alto que lo haga <= n( i ^ floor(log(n) / log(i)))

F=(n,i=n)=>i?[...((P=j=>i%--j?P(j):1==j)(i)?[i**((l=Math.log)(n)/l(i)|0)]:[]),...F(n,--i)]:[]