Eine Primzahlpotenz ist eine positive ganze Zahl n das kann in der Form geschrieben werden , n = p ^k wobei p eine Primzahl ist und k eine positive ganze Zahl. Zum Beispiel sind einige Primkräfte [2, 3, 5, 4, 9, 25, 8, 27, 125].

Als nächstes betrachten [2, 4, 8, 16, ...]wir Primzahlen von 2. Diese sind und können in der Form 2 ^{k geschrieben werden} . Sie werden alle berücksichtigt, wenn Primzahlen unter 20 berücksichtigt werden. 16 ist jedoch die maximale Primzahl mit einer Basisprimzahl von 2 in diesem Bereich. Eine Primzahlleistung p ^k ist maximal in einem Bereich, wenn es die höchste Leistung von p in diesem Bereich ist. Wir sind nur an der maximalen Primleistung in jedem Bereich interessiert , daher müssen alle niedrigeren Primleistungen ausgeschlossen werden.

Ihr Ziel ist es, eine Funktion oder ein Programm zu schreiben, das eine positive ganze Zahl n annimmt und die maximalen Primzahlen im Bereich ausgibt [2, 3, 4, ..., n].

Vielen Dank an @ Peter Taylor für die Klärung der Definition von maximaler Primkraft und mehr.

Regeln

• Das ist Code-Golf, also mach deinen Code so kurz wie möglich.
• Die maximalen Primzahlen können in beliebiger Reihenfolge ausgegeben werden, es dürfen jedoch keine Duplikate vorhanden sein.

Testfälle

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]

Die vollständige Liste der maximalen Primzahlen für 10000 finden Sie hier .

Gelee , 7 4 Bytes

æḟÆR

Probieren Sie es online!

Wie es funktioniert

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

4 Bytes gespart dank Meilen und Martin Ender

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

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

⌊und ⌋sind die 3Byte - Zeichen U+230Aund U+230Bdarstellen \[LeftFloor]und \[RightFloor], respectively.

Erläuterung:

Funktion pur. #ist die Abkürzung für Slot[1]das erste Argument für die Function. PrimePi@#zählt die Anzahl der Primzahlen, die kleiner oder gleich sind #, Range@PrimePi@#ist die Liste der ersten PrimePi[#]positiven Ganzzahlen, und ebenso Prime@Range@PrimePi@#die Liste der Primzahlen, die kleiner oder gleich sind #(dies ist ein Byte kürzer als Select[Range@#,PrimeQ]). Das Symbol xist Setgleich dieser Liste, dann in die angehobene Power ⌊x~Log~#⌋, das ist die Liste der Floor[Log[n,#]]für jeden nin x. In Mathematica führt das Erhöhen einer Liste auf die Powereiner anderen Liste gleicher Länge zu einer Liste der Potenzen der entsprechenden Elemente.

MATL, 13 Bytes

ZqG:!^tG>~*X>

Probieren Sie es online!

Erläuterung

        % 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

Gelee , 8 Bytes

ÆR*ÆE€»/

Probieren Sie es online!

Wie es funktioniert

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

Gelee , 12 9 Bytes

RÆEz0iṀ$€

Probieren Sie es online! (Methode ist für den 10000-Fall zu langsam).

Wie?

Erstellt die Liste von p ^k in der Reihenfolge von 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

Probieren Sie es hier aus!

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

Ich habe eine Weile nicht mehr mit Pyth gespielt, daher sind alle Golftipps willkommen.

Ich könnte keine kürzere Mathematica-Lösung bekommen als die von ngenisis , aber ich dachte, ich würde ein paar (hoffentlich interessante) alternative Ansätze anbieten.

Mathematica, 65 Bytes

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

Zuerst {#,#}&/@Range@#~Select~PrimeQerstellen wir eine Liste aller Primzahlen im entsprechenden Bereich, aber mit geordneten Paaren jeder Primzahl, wie { {2,2}, {3,3}, ...}. Dann bearbeiten wir diese Liste wiederholt mit der Ersetzungsregel {a_,b_}/;a<=#:>{b a,b}, die das erste Element des geordneten Paares mit dem zweiten multipliziert, bis das erste Element die Eingabe überschreitet. Dann wenden wir #/#2&@@@für jedes geordnete Paar das erste Element dividiert durch das zweite an. (Sie werden nach der zugrunde liegenden Primzahl sortiert. Ein Beispiel für die Ausgabe ist {16, 9, 5, 7, 11, 13, 17, 19}.)

Mathematica, 44 Bytes

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

Die von Mangoldt-Funktion Λ(n)ist eine interessante Funktion der Zahlentheorie: Sie ist gleich 0, sofern es sich nicht num eine Primzahl p ^k handelt. In diesem Fall ist sie gleich log p(nicht log n). (Dies sind natürliche Protokolle, aber es spielt keine Rolle.) Dadurch MangoldtLambda@#->#&~Array~#wird ein Array von Regeln erstellt, { 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }dessen Länge die ganze Zahl der Eingabe ist.

Wir wandeln dann diese Liste von Regeln in eine "Assoziation" mit <|...|>. Dies hat zur Folge, dass nur die letzte Regel mit einem bestimmten Wert für die linke Hand beibehalten wird. Mit anderen Worten, wirft es weg Log[2]->2und Log[2]->4und Log[2]->8und hält nur Log[2]->16(unter der Annahme , dass der Eingang zwischen 16 und 31 in diesem Beispiel ist). Die einzigen verbleibenden rechten Seiten sind daher die maximalen Primzahlen - mit Ausnahme der einen verbleibenden Regel 0->n, bei der ndie größte Nichtprimzahl bis zur Eingangszahl ist. Aber Restwirft diese unerwünschte Regel weg und Valuesextrahiert die rechten Seiten aus den Regeln in der Assoziation. (Sie enden wie oben sortiert.)

Eine etwas längere (46 Bytes) Version, die die Anzahl der Auftritte jedes einzelnen zählt log pund dann potenziert, um sie in die maximalen Primzahlen umzuwandeln:

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

CJam , 21 20 Bytes

Dank Martin Ender 1 Byte gespeichert

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

Probieren Sie es online!

Erläuterung

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×ᵐ

Probieren Sie es online!

Dies gibt die Leistungen vom größten zum kleinsten aus.

Das ist sehr ineffizient.

Erläuterung

⟧                   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

Dies findet die größten Primzerlegungen für jede Primzahl zuerst, und zwar aufgrund der Funktionsweise ⊇: von links nach rechts und von der größten zur kleinsten Teilmenge.

Brachylog , 24 21 19 Bytes

3 + 2 Bytes gespart dank Fatalize!

Es ist das erste Mal, dass ich Brachylog benutze und ich weiß, dass einige Dinge auf kürzere Weise hätte erledigt werden können, aber ich bin froh, dass es überhaupt funktioniert: D

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

Probieren Sie es online! (Rückgabewerte werden nach ihren Basisprimzahlen sortiert)

Erläuterung:

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

Probieren Sie es online!

Erläuterung

ƒ             # 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 + GNU-Dienstprogramme, 74 Bytes

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

Probieren Sie es online!

Die eingegebene Nummer wird als Argument übergeben. Die Ausgabe wird auf Standard gedruckt. (Stderr wird wie üblich ignoriert.)

Beispielausgabe:

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

So funktioniert das:

Nenne das Argument N.

seqgeneriert alle Zahlen von 1 bis N und factorfaktorisiert sie alle.

Der reguläre Ausdruck im Aufruf von sed identifiziert die Zeilen, in denen die Zahl ein Primzahl P ist, und ersetzt diese Zeilen durch Zeilen der Form `

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

(wobei P und N durch ihre tatsächlichen numerischen Werte ersetzt werden und alles andere buchstäblich kopiert wird, auch die Anführungszeichen und Semikolons sowie die Zeichenfolge print).

Diese Zeilen werden als Eingabe für bc -l; bc druckt die Werte der drei angegebenen Zahlen, gefolgt von einer neuen Zeile, und druckt dann die Zeichen /^p. (In bc bezeichnet l (x) den natürlichen Logarithmus von x.) JK K

Die Zeichenfolgen, die bc druckt, werden dann als Eingabe in dc eingespeist. dc gibt den Wert jedes P ^ (log (N) / log (P)) unter Verwendung von Ganzzahlarithmetik (Abschneiden) aus; das ist die größte Potenz von P, die <= N ist.

Eine Sache, die oben beschönigt wurde, ist, was mit Linien passiert, die durch Faktoren erzeugt werden, die nicht mit Primzahlen korrespondieren. Diese Zeilen stimmen nicht mit dem regulären Ausdruck im Aufruf von sed überein, daher wird für diese keine Ersetzung vorgenommen. Infolgedessen beginnen diese Zeilen mit einer Zahl, gefolgt von einem Doppelpunkt, der einen Fehler erzeugt, wenn er als Eingabe für eingegeben wird bc. Aber bc druckt nur nach stderr, was wir ignorieren. es druckt nichts zu stdout. Standardmäßig wird stderr in PPCG ignoriert .

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

Probieren Sie es online! Verwendung:

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

Edit: 6 Bytes weg dank Zgarb!

Erläuterung:

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

Gelee , 9 Bytes

Ræl/ÆF*/€

Ein Byte länger als meine andere Antwort , aber die Eingabe von 10.000 dauert ein paar Sekunden.

Probieren Sie es online!

Wie es funktioniert

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 Byte

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

Vorschläge sind willkommen. Dies ist etwas lang, aber es schien sich zu lohnen, es zu veröffentlichen, da alle Teilbarkeitstests explizit durchgeführt werden, anstatt mit Primzahlen verknüpfte integrierte Funktionen zu verwenden.

Anmerkungen:

• Eine natürliche Zahl q ist eine Primzahl <=> Alle Teiler von q sind Potenzen derselben Primzahl <=> für jedes d, das q teilt. Eines von d und q / d ist ein Teiler des anderen.
• Wenn q eine Potenz von p ist, ist q maximal <=> q ​​* p> n <=> q ​​* d> n für jeden nichttrivialen Divisor d von q.

Salbei, 43 Bytes

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

Ordnet jeder Primzahl im Bereich primes(i)ihre maximale Primzahlstärke zu. lnist nur ein Alias ​​von, logso dass es alternative Basen akzeptiert, obwohl der Name andeutet, dass es nur base verwenden kann 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]]

--aktualisiert nach Laikonis Feedback

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]

Definiert eine Funktion f. Probieren Sie es online!

Erläuterung

Die Idee ist, den Bereich [2..n]nach jenen Zahlen zu filtern, die kbefriedigen k == p^length(divisors k)und von p*k > ndenen pder kleinste Primteiler ist 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

nur ein bisschen echte Mathematik ...

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

Nervenzusammenbruch

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

Iterieren Sie rekursiv ivon 0 bis einschließlich n. Wenn iPrime ist, erhöhe es auf den höchsten Exponenten, der es erzeugt <= 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)]:[]