Uma potência principal é um número inteiro positivo n que pode ser escrito na forma n = p ^{k, em} que p é um número primo e k é um número inteiro positivo. Por exemplo, alguns poderes principais são [2, 3, 5, 4, 9, 25, 8, 27, 125].

Em seguida, considere potências primárias de 2. Essas são [2, 4, 8, 16, ...]e podem ser escritas no formato 2 ^k . Todos seriam incluídos ao considerar potências primárias abaixo de 20. No entanto, 16 é a potência primária máxima com uma base primária de 2 nesse intervalo. Um primo de energia p ^k é máxima em um intervalo se ele é o mais alto poder de p nesse intervalo. Estamos interessados ​​apenas na potência primária máxima em cada faixa, portanto todas as potências primárias inferiores devem ser excluídas.

Seu objetivo é escrever uma função ou programa que use um número inteiro positivo n e produza as potências primárias máximas no intervalo [2, 3, 4, ..., n].

Agradecemos a Peter Taylor por esclarecer a definição de potência primária máxima e muito mais.

Regras

• Isso é código-golfe, então faça seu código o mais curto possível.
• As potências primárias máximas podem ser emitidas em qualquer ordem, mas não deve haver duplicatas.

Casos de teste

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]

A lista completa de potências primárias máximas para 10000 pode ser encontrada aqui .

Geléia , 7 4 bytes

æḟÆR

Experimente online!

Como 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

Economizou 4 bytes graças a milhas e Martin Ender

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

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

⌊e ⌋são os 3caracteres de byte U+230Ae U+230Brepresentam \[LeftFloor]e \[RightFloor], respectivamente.

Explicação:

Função pura. #é a abreviação de Slot[1]qual representa o primeiro argumento para o Function. PrimePi@#conta o número de números primos menor ou igual a #, Range@PrimePi@#é a lista dos primeiros PrimePi[#]números inteiros positivos e também Prime@Range@PrimePi@#a lista de números primos menor ou igual a #(este é um byte menor que Select[Range@#,PrimeQ]). O símbolo xé Setigual a esta lista, em seguida, elevada à Power ⌊x~Log~#⌋, que é a lista de Floor[Log[n,#]]para cada nno x. No Mathematica, elevar uma lista para Poweroutra lista do mesmo comprimento resulta na lista dos poderes de seus elementos correspondentes.

MATL, 13 bytes

ZqG:!^tG>~*X>

Experimente Online!

Explicação

        % 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

Geléia , 8 bytes

ÆR*ÆE€»/

Experimente online!

Como 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.

Geléia , 12 9 bytes

RÆEz0iṀ$€

Experimente online! (o método é muito lento para o caso 10000).

Quão?

Constrói a lista de p ^k na ordem 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]

Pitão, 13 bytes

m^ds.lQdfP_TS

Experimente aqui!

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

Eu não jogo com Pyth há algum tempo, então qualquer dica de golfe é apreciada.

Não consegui uma solução Mathematica mais curta que a da ngenisis , mas pensei em oferecer algumas abordagens alternativas (espero que interessantes).

Mathematica, 65 bytes

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

Primeiro, usamos {#,#}&/@Range@#~Select~PrimeQpara criar uma lista de todos os números primos no intervalo apropriado, mas com pares ordenados de cada número primo, como { {2,2}, {3,3}, ...}. Em seguida, operamos nessa lista repetidamente com a regra de substituição {a_,b_}/;a<=#:>{b a,b}, que multiplica o primeiro elemento do par ordenado por segundo até que o primeiro elemento exceda a entrada. Em seguida, aplicamos #/#2&@@@à saída, para cada par ordenado, o primeiro elemento dividido pelo segundo. (Eles acabam classificados pelo primo subjacente: um exemplo de saída é {16, 9, 5, 7, 11, 13, 17, 19}).

Mathematica, 44 bytes

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

A função von Mangoldt Λ(n)é uma função interessante da teoria dos números: é igual a 0, a menos que nseja uma potência principal ^pk , caso em que é igual a log p(não log n). (Estes são logs naturais, mas não importa.) Assim, MangoldtLambda@#->#&~Array~#cria uma série de regras{ 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... } cujo comprimento é o número inteiro de entrada.

Em seguida, transformamos essa lista de regras em uma "associação" usando <|...|>. Isso tem o efeito de reter apenas a última regra com qualquer valor à esquerda. Em outras palavras, ele vai deitar fora Log[2]->2e Log[2]->4e Log[2]->8e manter apenas Log[2]->16(partindo do princípio que a entrada está compreendida entre 16 e 31 para este exemplo). Portanto, os únicos lados direitos restantes são as potências primárias máximas - exceto a regra restante 0->n, onde né a maior potência não primária até o número inteiro de entrada. Mas Restjoga fora essa regra indesejada e Valuesextrai o lado direito das regras da associação. (Eles acabam classificados como acima.)

Uma versão um pouco mais longa (46 bytes), que conta o número de aparências de cada uma log pe depois exponencia a conversão para as potências primárias máximas:

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

CJam , 21 20 bytes

Guardado 1 byte graças a Martin Ender

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

Experimente online!

Explicação

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

Braquilog , 15 bytes

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

Experimente online!

Isso gera os poderes do maior para o menor.

Isso é muito ineficiente.

Explicação

⟧                   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

Ele encontrará as maiores decomposições primárias para cada primo primeiro, devido à maneira como ⊇funciona: da esquerda para a direita e do maior para o menor subconjunto.

Braquilog , 24 21 19 bytes

3 + 2 bytes salvos graças ao Fatalize!

Esta é a minha primeira vez usando Brachylog, e sei que algumas coisas poderiam ter sido feitas de maneiras mais curtas, mas estou feliz que funcione: D

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

Experimente online! (Os valores retornados são ordenados por seus primos base)

Explicação:

{................}ᶠ           #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,

Experimente online!

Explicação

ƒ             # 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

Utilitários Bash + GNU, 74 bytes

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

Experimente online!

O número de entrada é passado como argumento. A saída é impressa em stdout. (Como é habitual, stderr é ignorado.)

Saída de amostra:

./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

Veja como funciona:

Chame o argumento N.

seqgera todos os números de 1 a N e factorfatora todos eles.

O regex na chamada para sed identifica as linhas em que o número é um P primo e substitui essas linhas por linhas com a forma `

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

(onde P e N são substituídos por seus valores numéricos reais e todo o resto é copiado literalmente, até as aspas e ponto-e-vírgula e a sequência print).

Essas linhas são alimentadas como entrada para bc -l; bc imprime os valores dos três números indicados, cada um seguido por uma nova linha e, em seguida, imprime os caracteres /^p. (Em bc, l (x) denota o logaritmo natural de x.) JK K

As strings que bc imprime são então alimentadas como entrada para dc; dc imprime o valor de cada P ^ (log (N) / log (P)) usando aritmética inteira (truncando); esse é o maior poder de P que é <= N.

Uma coisa que foi encoberta acima é o que acontece com as linhas produzidas por fatores que não correspondem a números primos. Essas linhas não correspondem ao regex na chamada para sed, portanto, nenhuma substituição é feita nessas. Como resultado, essas linhas começam com um número seguido de dois pontos, que gera um erro quando alimentado como entrada para bc. Mas bc apenas imprime para stderr então, o que ignoramos; não imprime nada no stdout. Por padrão, stderr é ignorado no 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]]

Experimente online! Uso:

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

Edit: 6 bytes de desconto graças ao Zgarb!

Explicação:

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

Geléia , 9 bytes

Ræl/ÆF*/€

Um byte mais longo que minha outra resposta , mas termina com a entrada de 10.000 segundos.

Experimente online!

Como 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)))

Sugestões são bem-vindas. Isso é meio longo, mas parecia valer a pena postar, porque ele faz todo o teste de divisibilidade explicitamente, em vez de usar os built-ins relacionados aos números primos.

Notas:

• Um número natural q é um poder primo <=> todos os divisores de q são potências do mesmo primo <=> para qualquer d que divide q, um de d e q / d é um divisor do outro.
• Se q é uma potência de p, q é máximo <=> q ​​* p> n <=> q ​​* d> n para cada divisor não trivial d de q.

Sábio, 43 bytes

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

Mapeia cada prime no intervalo primes(i)para sua potência máxima no prime. lné apenas um alias de, logportanto, ele aceita bases alternativas, embora seu nome sugira que ele possa usar apenas 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]]

- atualizado pelo feedback 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 uma função f. Experimente online!

Explicação

A idéia é filtrar o intervalo [2..n]para os números kque satisfazem k == p^length(divisors k)e p*k > n, onde pé o menor divisor principal 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

apenas um pouco 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);

demolir

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

Faça iterações recursivas ide 0 até e inclusive n. Se ié raise prime-lo ao mais alto expoente piso que torna <= 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)]:[]