Une puissance première est un entier positif n qui peut s'écrire sous la forme n = p ^k où p est un nombre premier et k est un entier positif. Par exemple, certains pouvoirs principaux le sont [2, 3, 5, 4, 9, 25, 8, 27, 125].

Ensuite, considérons des puissances premières de 2. Celles-ci sont [2, 4, 8, 16, ...]et peuvent être écrites sous la forme 2 ^k . Ils seraient tous inclus lorsque l'on considère les puissances premières inférieures à 20. Cependant, 16 est la puissance première maximale avec un nombre premier de base de 2 dans cette plage. Une puissance première p ^k est maximale dans une plage si elle est la puissance la plus élevée de p dans cette plage. Nous ne sommes intéressés que par la puissance primaire maximale dans chaque plage, donc toutes les puissances primaires inférieures doivent être exclues.

Votre objectif est d'écrire une fonction ou un programme qui prend un entier positif n et génère les puissances premières maximales dans la plage [2, 3, 4, ..., n].

Merci à @ Peter Taylor d' avoir clarifié la définition de la puissance maximale maximale et plus encore.

Règles

• C'est du code-golf, alors faites votre code le plus court possible.
• Les puissances premières maximales peuvent être émises dans n'importe quel ordre mais il ne doit pas y avoir de doublons.

Cas de test

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 liste complète des puissances premières maximales pour 10000 peut être trouvée ici .

Gelée , 7 4 octets

æḟÆR

Essayez-le en ligne!

Comment ça marche

æḟÆ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 octets

4 octets enregistrés grâce aux miles et à Martin Ender

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

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

⌊et ⌋sont les 3caractères d'octet U+230Aet U+230Breprésentant \[LeftFloor]et \[RightFloor], respectivement.

Explication:

Fonction pure. #est l'abréviation de Slot[1]qui représente le premier argument du Function. PrimePi@#compte le nombre de nombres premiers inférieurs ou égaux à #, Range@PrimePi@#est la liste des premiers PrimePi[#]entiers positifs, ainsi que Prime@Range@PrimePi@#la liste des nombres premiers inférieurs ou égaux à #(c'est un octet plus court que Select[Range@#,PrimeQ]). Le symbole xest Setégal à cette liste, puis élevé à la Power ⌊x~Log~#⌋, qui est la liste de Floor[Log[n,#]]pour chaque nentrée x. Dans Mathematica, élever une liste vers Powerune autre liste de même longueur donne la liste des puissances de leurs éléments correspondants.

MATL, 13 octets

ZqG:!^tG>~*X>

Essayez-le en ligne!

Explication

        % 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ée , 8 octets

ÆR*ÆE€»/

Essayez-le en ligne!

Comment ça marche

Æ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ée , 12 9 octets

RÆEz0iṀ$€

Essayez-le en ligne!(la méthode est trop lente pour le cas 10000).

Comment?

Construit la liste de p ^k par ordre 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 octets

m^ds.lQdfP_TS

Essayez-le ici!

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

Je n'ai pas joué avec Pyth depuis un moment donc tous les conseils de golf sont appréciés.

Je ne pouvais pas obtenir une solution Mathematica plus courte que la solution de ngenisis , mais j'ai pensé proposer deux approches alternatives (espérons-le intéressantes).

Mathematica, 65 octets

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

Nous utilisons {#,#}&/@Range@#~Select~PrimeQd' abord pour construire une liste de tous les nombres premiers dans la plage appropriée, mais avec des paires ordonnées de chaque nombre premier, comme { {2,2}, {3,3}, ...}. Ensuite, nous opérons sur cette liste à plusieurs reprises avec la règle de remplacement {a_,b_}/;a<=#:>{b a,b}, qui multiplie le premier élément de la paire ordonnée par le second jusqu'à ce que le premier élément dépasse l'entrée. Ensuite, nous appliquons #/#2&@@@à la sortie, pour chaque paire ordonnée, le premier élément divisé par le second. (Ils finissent par être triés par nombre premier sous-jacent: un exemple de sortie est {16, 9, 5, 7, 11, 13, 17, 19}.)

Mathematica, 44 octets

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

La fonction de von Mangoldt Λ(n)est une fonction de théorie des nombres intéressante: elle est égale à 0 sauf si elle nest une puissance première p ^k , auquel cas elle est log p(non log n). (Ce sont des journaux naturels, mais cela n'a pas d'importance.) MangoldtLambda@#->#&~Array~#Crée ainsi un tableau de règles { 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }dont la longueur est l'entier en entrée.

Nous transformons ensuite cette liste de règles en une "association" en utilisant <|...|>. Cela a pour effet de ne conserver que la dernière règle avec une valeur de gauche donnée. En d'autres termes, il supprimera Log[2]->2et Log[2]->4et Log[2]->8et conservera uniquement Log[2]->16(en supposant que l'entrée est comprise entre 16 et 31 pour cet exemple). Par conséquent, les seuls côtés droits restants sont les puissances premières maximales - à l'exception de la seule règle restante 0->n, où nest la plus grande puissance non principale jusqu'à l'entier d'entrée. Mais Restjette cette règle indésirable et Valuesextrait le côté droit des règles de l'association. (Ils finissent par être triés comme ci-dessus.)

Une version légèrement plus longue (46 octets), qui compte le nombre d'apparitions de chacun log ppuis exponenti pour se convertir aux puissances premières maximales:

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

CJam , 21 20 octets

1 octet enregistré grâce à Martin Ender

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

Essayez-le en ligne!

Explication

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 octets

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

Essayez-le en ligne!

Cela délivre les puissances du plus grand au plus petit.

C'est très inefficace.

Explication

⟧                   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

Cela trouvera les plus grandes décompositions principales pour chaque premier en raison de la façon dont ⊇fonctionne: de gauche à droite et du plus grand au plus petit sous-ensemble.

Brachylog , 24 21 19 octets

3 + 2 octets économisés grâce à Fatalize!

C'est ma première utilisation de Brachylog, et je sais que certaines choses auraient pu être faites de manière plus courte, mais je suis heureux que cela fonctionne même: D

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

Essayez-le en ligne! (Les valeurs de retour sont ordonnées par leurs nombres premiers de base)

Explication:

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

ƒNpiN¹N.nïm,

Essayez-le en ligne!

Explication

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

Utilitaires Bash + GNU, 74 octets

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

Essayez-le en ligne!

Le numéro d'entrée est passé en argument. La sortie est imprimée sur stdout. (Comme d'habitude, stderr est ignoré.)

Exemple de sortie:

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

Voici comment cela fonctionne:

Appelez l'argument N.

seqgénère tous les nombres de 1 à N et les factorfactorise tous.

Le regex dans l'appel à sed identifie les lignes où le nombre est un P premier, et remplace ces lignes par des lignes qui ont la forme `

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

(où P et N sont remplacés par leurs valeurs numériques réelles, et tout le reste est copié littéralement, même les guillemets et les points-virgules, et la chaîne print).

Ces lignes sont alimentées en entrée vers bc -l; bc imprime les valeurs des trois nombres indiqués, chacune suivie d'une nouvelle ligne, puis imprime les caractères /^p. (En bc, l (x) désigne le logarithme naturel de x.) JK K

Les chaînes que bc imprime sont ensuite introduites en entrée dans dc; dc imprime la valeur de chaque P ^ (log (N) / log (P)) en utilisant l'arithmétique entière (tronquée); c'est la plus grande puissance de P qui est <= N.

Une chose qui est passée sous silence est ce qui arrive aux lignes qui sont produites par des facteurs qui ne correspondent pas aux nombres premiers. Ces lignes ne correspondent pas à l'expression régulière dans l'appel à sed, donc aucun remplacement n'est effectué sur celles-ci. Par conséquent, ces lignes commencent par un nombre suivi d'un deux-points, ce qui génère une erreur lors de son alimentation en entrée bc. Mais bc imprime alors sur stderr, ce que nous ignorons; il n'imprime rien sur stdout. Par défaut, stderr est ignoré sur PPCG .

Haskell , 73 67 66 octets

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

Essayez-le en ligne! Usage:

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

Edit: 6 octets de réduction grâce à Zgarb!

Explication:

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ée , 9 octets

Ræl/ÆF*/€

Un octet de plus que mon autre réponse , mais se termine pour l'entrée 10 000, c'est quelques secondes.

Essayez-le en ligne!

Comment ça marche

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 112 105 octets

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

Suggestions bienvenues. C'est un peu long, mais cela semblait valoir la peine d'être publié car il effectue tous les tests de divisibilité de manière explicite plutôt que d'utiliser des éléments intégrés liés aux nombres premiers.

Remarques:

• Un nombre naturel q est une puissance première <=> tous les diviseurs de q sont des puissances du même nombre premier <=> pour tout d qui divise q, l'un de d et q / d est un diviseur de l'autre.
• Si q est une puissance de p, q est maximal <=> q ​​* p> n <=> q ​​* d> n pour chaque diviseur non trivial d de q.

Sauge, 43 octets

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

Mappe chaque prime dans la plage primes(i) à sa puissance maximale maximale. lnn'est qu'un alias de logdonc il accepte des bases alternatives bien que son nom suggère qu'il ne peut utiliser que la base e.

Haskell, 110 90 octets

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]]

- mis à jour selon les commentaires de Laikoni

Haskell , 70 octets

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

Définit une fonction f. Essayez-le en ligne!

Explication

L'idée est de filtrer la plage [2..n]pour les nombres kqui satisfont k == p^length(divisors k)et p*k > n, où pest le plus petit diviseur premier 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 octets

juste un peu de vrais maths ...

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

panne

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 octets

Itérer récursivement ide 0 à et y compris n. Si iest premier, élevez-le au plus haut exposant au sol qui le fait <= 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)]:[]