Prime oder höchster Faktor

14

Herausforderung:

Überprüfen Sie bei einem Array nicht negativer ganzer Zahlen im Bereich von0 to Infinity , ob alle Primzahlen sind oder nicht. (Sie können die Eingabe auch als Zeichenfolge übernehmen, wenn Sie möchten.)

Eingang:

Eingabe: Ein Array von Zahlen

Ausgabe: Das Array, bei dem jedes Element durch eines der folgenden Elemente ersetzt wird:

-1                 -----> If 0, 1
1                  -----> If it is a prime number greater than 1
the highest factor -----> If that number is not prime

Rückgabe entweder -1 (0, 1), 1 (für Primzahlen> = 2) oder des höchsten Faktors der angegebenen Zahl (für Nicht-Primzahlen)

Beispiele:

[1, 2, 3, 4, 10, 11, 13]                        ---> [-1, 1, 1, 2, 5, 1, 1]
[100, 200, 231321, 12312, 0, 111381209, 123123] ---> [50, 100, 77107, 6156, -1, 1, 41041]

Hinweis:

Die Eingabe ist immer gültig, dh sie besteht nur aus Zahlen und Dezimalstellen, auf die nicht geprüft wurde. Das Array kann leer sein. Wenn dies der Fall ist, geben Sie das leere Array zurück.

Beschränkung:

Dies ist so dass der kürzeste Code in Bytes für jede Sprache gewinnt.

Bestenliste :

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

# Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes


quelle
2
Ich empfehle dringend, die Sandbox für zukünftige Fragen zu verwenden, um vor dem Posten Feedback zu Fragen zu geben
Jo King,
@Joking: Für unendlich müssen Sie alle Zahlen bis unendlich ausgeben. Dies ist nur für Sie und Sie müssen auch sicherstellen, dass es keine Zeitüberschreitung gibt. JK:
4
wollte nur feststellen, dass in "Wenn es eine Primzahl größer als 1 ist" größer als 1 wirklich nicht notwendig ist, weil Primzahlen immer größer als 1 sind
Ivo Beckers
5
Höchsten Faktor definieren. Soll ich die Nummer selbst zurückgeben? Die höchste teilbare Primzahl? Der höchste Faktor, der nicht selbst ist?
Nissa
2
Ich gehe davon aus, dass unsere Programme nur für Ganzzahlen bis zur maximalen Ganzzahlgröße der von uns gewählten Sprache funktionieren müssen (für diejenigen, die keine Unterstützung für beliebig große Ganzzahlen haben)
JDL

Antworten:

9

Gelee ,  7 6 Bytes

ÆḌṪ€o-

Ein monadischer Link, der eine Liste nicht negativer Ganzzahlen akzeptiert und eine Liste von Ganzzahlen größer oder gleich -1 beibehält.

Probieren Sie es online!

Wie?

Beachten Sie, dass:

  • Alle Primzahlen haben einen einzigen Divisor (einen)
  • Alle Komposite haben mehrere richtige Teiler (einer plus die anderen)
  • Keine Zahl hat sich als richtiger Teiler
  • Jellys get-proper-divisors-Atom ÆḌliefert eine Liste der richtigen Teiler in aufsteigender Reihenfolge
  • Null und Eins haben keine richtigen Teiler (sie sind weder Primzahl noch Komposit)
  • Das Anwenden von Jellys Schwanzatom auf eine leere Liste ergibt Null
  • Keine Zahl hat einen richtigen Teiler von Null (geschweige denn die maximale)
  • Alle Zahlen ungleich Null sind in Jelly wahr, während Null falsch ist

ÆḌṪ€o- | Link: list of integers   e.g. [ 0, 1,  2,  5,     10,    5183]
ÆḌ     | proper divisors (vectorises)  [[],[],[1],[1],[1,2,5],[1,71,73]]
  Ṫ€   | tail €ach                     [ 0, 0,  1,  1,      5,      73]
     - | literal minus one
    o  | logical OR (vectorises)       [-1,-1,  1,  1,      5,      73]
Jonathan Allan
quelle
8

Gelee , 9 8 Bytes

1 Byte dank @Dennis gespeichert

:ÆfṂ€$~~

Probieren Sie es online! oder führen Sie alle Testfälle aus

Kommentiert

Wir nutzen die Tatsache, dass beide nanund infwerden 0in Jelly, wenn ein bitweises NICHT auf sie angewendet wird.

:ÆfṂ€$~~ - main link, taking the input list
 ÆfṂ€$   - treat these two links as a monad:
 Æf      -   get the lists of prime factors (0 --> 0; 1 --> empty list; prime --> itself)
    €    -   for each list,
   Ṃ     -   isolate the minimum prime factor (turns empty lists into 0)
:        - divide each entry by its minimum prime factor (0/0 --> nan; 1/0 --> inf)
      ~~ - bitwise NOT x2 (nan or inf --> 0 --> -1; other entries are unchanged)
Arnauld
quelle
3
Sie haben diesmal kein JavaScript verwendet? nette Antwort übrigens
3
Ich mag das wirklich ~~. :ÆfṂ€$~~Spart ein Byte, indem die Hilfsverknüpfung entfernt wird.
Dennis
@ Tennis Ah! $ist, wonach ich gesucht habe. :) Vielen Dank!
Arnauld
7

R, 68 62 Bytes

Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())

Eine Lösung, die nur Base R verwendet, keine Bibliotheken! Vielen Dank an Giuseppe für die 6 Bytes.

Verwendet scan, um eine durch Leerzeichen getrennte Liste von Zahlen einzulesen, um %%zu identifizieren, welche Faktoren sind. venthält dann einen Vektor aller Faktoren in aufsteigender Reihenfolge (einschließlich 1 und n). Dies hat die nette Eigenschaft, dass, wenn wir es reversetzen v, die gewünschte Nummer an zweiter Stelle steht, um einen teuren Anruf zu vermeiden lengthoder tail(wenn nes Primzahl war, venthält es n 1, sonst enthält es)n (factors in descending order) 1 ).

Beispielausgabe (TIO Link hier ):

> Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())
1: 0 1 2 3 4 5 6 7 8 9
11: 
Read 10 items
[[1]]
[1] -1

[[2]]
[1] -1

[[3]]
[1] 1

[[4]]
[1] 1

[[5]]
[1] 2

[[6]]
[1] 1

[[7]]
[1] 3

[[8]]
[1] 1

[[9]]
[1] 4

[[10]]
[1] 3

Wenn Sie der Meinung sind, dass eine Liste kein akzeptabler Rückgabetyp ist, tauschen Sie sie Mapaus sapplyund fügen Sie 3 Bytes hinzu.

JDL
quelle
2
62 Bytes
Giuseppe
nett - hätte nicht gedacht, mit zu initialisieren!
JDL
6

05AB1E , 11 9 8 Bytes

Ñε¨àDd<+

-3 Bytes dank @Emigna , wechselt ©d1-®+zu Dd<+und €¨€ànach ε¨à.

Nur meine zweite 05AB1E Antwort kann also definitiv golfen werden .

Probieren Sie es online aus.

Erläuterung:

Ñ           # Divisors of each item in the input-list (including itself)
            #  [1,2,10,3] → [[1],[1,2],[1,2,5,10],[1,2,3]]
 ε          # For each:
  ¨         #  Remove last item (so it's now excluding itself)
            #   [[1],[1,2],[1,2,5,10],[1,2,3]] → [[],[1],[1,2,5],[1,2]]
   à        #  And get the max
            #   [[],[1],[1,2,5],[1,2]] → ['',1,5,2]
    D       # Duplicate the list
     d      # Is it a number (1 if it's a number, 0 otherwise)
            #  ['',1,5,2] → [0,1,1,1]
      <     # Subtract 1
            #  [0,1,1,1] → [-1,0,0,0]
       +    # Add both lists together
            #  ['',1,5,2] and [-1,0,0,0] → ['-1',1,5,2]
Kevin Cruijssen
quelle
1
Dd<+sollte funktionieren statt ©d1-®+. Das brauchst du auch nicht, ïda sie noch ints sind. Sie könnten es in der Fußzeile haben, um eine schönere Ausgabe zu erhalten.
Emigna
@Emigna Ah, 1-stattdessen <war das ziemlich doof .. Danke für die Dstattdessen ©...®! Und das habe ich ja ïjetzt in die Fußzeile gestellt.
Kevin Cruijssen
1
Oder noch besser:Ñε¨àDd<+
Emigna
Viel besser als mein 12-Byter.
Magic Octopus Urn
5

J , 21 Bytes

_1:`(%{.@q:)@.(>&1)"0

Probieren Sie es online!

Erläuterung:

(>&1)"0 ist jede Zahl größer als 1?

@. Wenn nicht, kehre zurück _1:

(%{.@q:)Wenn es 2 oder mehr ist, teilen Sie %die Zahl durch den ersten {.der Primfaktorenq:

Galen Ivanov
quelle
4

Japt , 6 Bytes

Nach dem Golfen war er fast identisch mit und genauso kurz wie Jonathans Lösung.

®â¬ÌªJ

Versuch es


Erläuterung

®          :Map
 ⬠       :  Proper divisors
   Ì       :  Get last element (returns null if the array is empty)
    ª      :  Logical OR
     J     :  -1
Zottelig
quelle
Speichern Sie ein Byte mit-m
Oliver
3

Python 3 , 62 Bytes

lambda l:[max([k for k in range(1,n)if n%k<1]+[-1])for n in l]

Probieren Sie es online!

Für 0und 1 range(1,n)ist leer, daher wird der Code zu ausgewertet max([]+[-1]) = -1. Bei Primzahlen ist der einzige Teiler in [1, n) 1der gewünschte Ausgang.


Kokosnuss , 50 Bytes

map$(n->max([k for k in range(1,n)if n%k<1]+[-1]))

Probieren Sie es online!

ovs
quelle
3

Java 8, 105 103 87 Bytes

a->{for(int i=a.length,n,x;i-->0;a[i]=n<2?-1:n/x)for(n=a[i],x=1;++x<n;)if(n%x<1)break;}

Ändert das Eingabearray, anstatt ein neues zurückzugeben, um Bytes zu sparen.

Probieren Sie es online aus.

Erläuterung:

a->{                  // Method with integer-array parameter and no return-type
  for(int i=a.length,n,x;i-->0;
                      //  Loop backward over the array
      a[i]=           //    After every iteration: change the current item to:
           n<2?       //     If the current item is 0 or 1:
            -1        //      Change it to -1
           :          //     Else:
            n/x)      //      Change it to `n` divided by `x`
     for(n=a[i],      //   Set `n` to the current item
         x=1;++x<n;)  //   Inner loop `x` in range [2,`n`)
       if(n%x<1)      //    If `n` is divisible by `x`:
         break;}      //     Stop the inner loop (`x` is now the smallest prime-factor)
                      //   (if the loop finishes without hitting the `break`,
                      //    it means `n` is a prime, and `x` and `n` will be the same)
Kevin Cruijssen
quelle
3

Haskell, 52 49 Bytes

map(\x->last$[d|d<-[1..x-1],mod x d<1]++[-1|x<2])

Probieren Sie es online!

map                     -- for each element in the input array
  \x->                  -- apply the lambda function
    last                -- pick the last element of the following list
     [d|d<-[1..x-1]     --  all d from 1 to x-1 
           ,mod x d<1]  --    where d divides x 
     ++[-1|x<2]         --  followed by -1 if x<2
nimi
quelle
3

Schale , 8 Bytes

m(|_1→hḊ

Probieren Sie es online!

Erläuterung

m(|_1→hḊ  Implicit Input         [1,2,3,4,10]
m(        Map each element
       Ḋ    List of divisors     [[1],[1,2],[1,3],[1,2,4],[1,2,5,10]]
     →h     Penultimate element  [0,1,1,2,5]
  |_1       If falsy then -1     [-1,1,1,2,5]
Fyr
quelle
3

Attache , 23 Bytes

@{Max&-1!Divisors@_@-2}

Probieren Sie es online!

29 Bytes, ohne Punkte: @(Max&-1@Last@ProperDivisors)

24 Bytes, auch ohne Punkt: @(Max&-1@`@&-2@Divisors)

Dies wird einfach der vorletzte Teiler von ndann das Maximum davon und -1. Das vorletzte Element in einem Array mit weniger als zwei Elementen ist nilund Max[-1, nil]ist -1. @vektorisiert einfach diese Funktion und lässt sie auf jedes Atom zutreffen.

Conor O'Brien
quelle
2

R + numbers, 88 79 Bytes

Vielen Dank an die Kommentare für einige Ratschläge vor allem zur Einreichung von Beiträgen.

function(y)sapply(y,function(x)"if"(x<2,-1,prod(numbers::primeFactors(x)[-1])))

Verwendet das Produkt aller Primfaktoren mit Ausnahme des kleinsten und die Tatsache, dass das Produkt der Elemente eines leeren Vektors definiert ist 1 .

Probieren Sie es online!

ngm
quelle
1
Speichert Bytes, um den libraryAufruf wegzulassen und numbers::primeFactorsdirekt zu verwenden.
JDL
1
Hier ist ein TIO-Link , um zu sehen, was JDL vorschlägt, und um dies in eine anonyme Funktion umzuwandeln.
Giuseppe
2

Brachylog , 10 Bytes

{fkt|∧_1}ˢ

Probieren Sie es online!

Die folgende Erklärung wird zumeist der Kürze halber zwingend formuliert und spiegelt die deklarative Natur von Brachylog nicht genau wider.

{          Start of inline predicate.
           Implicit input to the predicate.
 f         Create a list of all of the input's factors (including itself).
  k        Remove the last item of this list so that it no longer contains the original number.
   t       Take the last item of the list with the last item removed.
           Implicitly unify the output with the aforementioned last item.
    |      If that failed, because one of the lists was empty...
     ∧     discarding the input, (there's probably some obvious reason ∨ won't work here but I don't know what it is)
      _1   unify the output with -1 instead.
        }  End of the inline predicate.
         ˢ For every item of the input, unify it with the predicate's input and get a list of the corresponding outputs.

Ich beschloss, Brachylog zu lernen, damit ich ein bisschen Spaß mit Codegolf haben konnte und hoffte, durch Osmose etwas über das Verhalten von tatsächlichem Prolog zu lernen Ausführungskontrollzeichen funktionieren.

Nicht verwandte Zeichenfolge
quelle
2
„Es gibt wahrscheinlich einige offensichtliche Grund ∨ funktioniert hier nicht , aber ich weiß nicht , was es ist“ -> Sie können .∨statt |∧(ich vermute , Sie das vergessen haben .), aber es ist das gleiche Byte - Zählung. Willkommen bei PPCG (und vor allem Brachylog: p) übrigens!
Fatalize
Ah, natürlich! Vielen Dank.
Unrelated String
Du kannst diese Art von Fragen zu Brachylog im Brachylog-Chatraum stellen
Fatalize
1

Stax , 14 13 Bytes

ü±p╞Ö*«òτ♀╣â▀

Führen Sie es aus und debuggen Sie es

Erklärung (ausgepackt):

m|fc%c{vsH1?}U? Full program, implicit input-parsing
m               Map
 |fc%c            Get factorisation and length of it (0 and 1 yield [])
      {     } ?   If length != 0:
       v            Decrement
           ?        If still != 0:
        sH            Last element of factorisation
           ?        Else:
          1           Push 1
              ?   Else:
             U      Push -1

Pseudocode innerhalb der Karte:

f = factorisation(i)
l = length(f)
if l:
    if --l:
        return f[-1]
    else:
        return 1
else:
    return -1
wastl
quelle
1

Pyth, 12 Bytes

me+_1f!%dTSt

Probieren Sie es hier aus

Erläuterung

me+_1f!%dTSt
m            Q    For each number d in the (implicit) input...
          Std     ... get the range [1, ..., d - 1]...
     f!%dT        ... take the ones that are factors of d...
  +_1             ... prepend -1...
 e                ... and take the last.

quelle
1

J , 14 Bytes

1(%0{q:,-)@>.]

Probieren Sie es online!

Nehmen Sie stattdessen für jede Zahl n das Maximum von (n, 1).
Hänge die negierte Zahl an die Liste ihrer Primfaktoren an (leere Liste für 1) und dividiere die Zahl durch den ersten Punkt in der Liste.

Auch 14 Bytes

(%0{q:) ::_1"0

Probieren Sie es online!

Teilen Sie jede Zahl durch den ersten ihrer Primfaktoren. 0 löst einen Domain-Fehler mit aus q:und wir suchen nach dem 0. Element in einer leeren Liste für 1 - das ist auch ein Fehler. Geben Sie für jede Zahl, die Fehler enthält, −1 zurück.

FrownyFrog
quelle
Sehr schöne Lösungen!
Galen Ivanov
1

Japt , 14 11 8 Bytes

®/k v)ªÉ
®        // For each input number,
 /k v    // return the number divided by it's first prime factor,
     )ªÉ // or -1 if such a number doesn't exist (the previous result is NaN).

Probieren Sie es online!

Dank Shaggy wurden diese drei nervigen Bytes abgeschabt .

Nit
quelle
Sie müssen die Primzahlen nicht filtern - kgibt die Primfaktoren von zurück N- dies ®/k v)ªÉ
Shaggy
@ Shaggy Danke, wusste nicht, dass es nur die Primfaktoren zurückgibt, da die Methodendokumente das nicht sagen.
Nit
1
Oh ja, das hab ich vergessen. Wollte für eine Weile einen PR für das einreichen; werde dies in Kürze tun.
Shaggy
1

JavaScript (Node.js) , 61 Byte

-6 Bytes dank @shaggy

_=>_.map(_=>eval('for(v=_/(d=_>>1);v!=~~v;v=_/--d);d'))

Probieren Sie es online!


Erklärung:

_ =>                                     // input i.e : the original array
    _.map(                               // map over all elements of the array
        eval('                           // eval a string
            for(v=_/(d=_>>1);            // set v = _ / _ >> 1 and set that to d
                v!=~~v;                  // and keep going until v !== floor(v)
                        v=_/d--);        // to _ / d again (d was changed)
                    d'                   // return d
            ))                           // end eval and map and function

Dies ist immer noch für alten Code nicht aktualisiert.

ES5 freundlich auch:

 const primeOrNot = function(input) { // the function with argument input
      return input.map(function(value) { // returns the array after mapping over them
           d = Math.floor(value * 0.5); // multiply each element by 0.5 and floor it 
           for(let v = value / d; v != Math.floor(v);) { // for loop goes until v!=~~v
                d --; // subtract one from d
                v = value / d; // set v again to value / d
           }
           return d; // return d
      })
 };
Muhammad Salman
quelle
55 Bytes
Shaggy
@ Shaggy: Danke
Muhammad Salman
1

Bash + GNU-Dienstprogramme, 49

  • 9 Bytes gespart dank @Cowsquack
factor|sed '/:$/c-1
/: \w+$/c1
s%: %/%
y/ /#/'|bc

Erläuterung

  • factor Liest Eingangsnummern von STDIN, eine pro Zeile und gibt sie im Format aus <input number>: <space-separated list of prime factors (ascending)>
  • sed verarbeitet dies wie folgt:
    • /:$/c-1 Die Eingangsnummern 0 und 1 haben keine Primfaktoren und werden durch ersetzt -1
    • /: \w+$/c1Zahlen mit einem Primfaktor sind Primzahlen. Ersetzen Sie diese durch1
    • s%: %/%Ersetzen :durch/ . Dadurch wird ein arithmetischer Ausdruck erstellt, um die (Nicht-Prim) -Eingabezahl durch ihren kleinsten Primfaktor zu teilen und den größten Faktor zu erhalten
    • y/ /#/ Entfernen Sie die Liste der anderen (nicht benötigten) Faktoren (durch Auskommentieren)
  • bc Arithmetisch auswerten und anzeigen

Probieren Sie es online!

Digitales Trauma
quelle
1
Möglicherweise können Sie das löschen -r, und für die ersten beiden skönnen Sie /regex/cvalueein Byte Golf spielen. Wenn Sie diesen regulären Ausdruck weiter vereinfachen, können Sie mehr sparen, und Sie können ein Byte in den letzten beiden regulären Ausdrücken speichern, indem Sie nur das :durch /, und ersetzen Kommentieren Sie dann den unerwünschten Teil wie folgt aus
Kritixi Lithos
@Cowsquack sehr gut - danke!
Digitales Trauma
1

Befunge-98 (FBBI) , 39 Bytes

j&:!+f0p1-1:::' -:!j;3k$.nbj;-\%!!j:1+a

Probieren Sie es online!

Endet mit dem & wenn keine Nummern mehr vorhanden sind. Dadurch wird das Programm 60 Sekunden lang angehalten, bis TIO das Programm beendet. Dies ist bei Befunge-98 unvermeidlich, zumindest bei TIO, da beide Interpreter dies tun. Nachdem Sie die Wiedergabe beendet haben, können Sie das Programm nach einer Weile stoppen, um zu sehen, was ausgegeben wird, wenn Sie die Minute gewartet haben.


Im Grunde genommen verwandelt es jede neue Zahl, wenn sie 0 ist, in eine 1. Dann legt es eine -1 auf den Stapel, gefolgt von einer Zahl, die von 1 beginnt und hochzählt, bis sie die eingegebene Zahl erreicht, in welchem ​​Fall sie Gibt die zweite Zahl auf dem Stapel aus (-1 für eine Eingabe von 0 oder 1 und den höchsten Faktor für andere). Jedes Mal, wenn wir die Schleife durchlaufen, fügen wir den Wert des Iterators dem Stapel dahinter hinzu, wenn ( input % iterator == 0). Dies bedeutet, dass wir bei der Eingabe nur den Iterator wegwerfen und drucken müssen. Dann räumen wir den Stapel mitn und kehren zur Leseeingabefunktion zurück.

Ich kann die Erklärung später erweitern, wir werden sehen ...

MilderMilquetoast
quelle
0

Retina 0.8.2 , 33 Bytes

%(`^0|^1$
-1
\d+
$*
^(1+)\1+$
$.1

Probieren Sie es online! Link enthält die Testfälle, die nicht zu langsam sind. Erläuterung:

%(`

Schleife über jede Eingangsnummer.

^0|^1$
-1

Sonderfall 0 und 1.

\d+
$*

In Unary konvertieren (hat keinen Einfluss auf -1).

^(1+)\1+$
$.1

Ersetzen Sie jede Zahl durch den größten korrekten Dezimalfaktor.

Neil
quelle
0

tinylisp , 75 bytes

(load library
(q((L)(map(q((N)(i(l N 2)(- 1)(/ N(min(prime-factors N))))))L

Probieren Sie es online! (Enthält 4 zusätzliche Bytes, um der anonymen Funktion einen Namen zu geben, damit wir sie in der Fußzeile aufrufen können.)

Ungolfed / Erklärung

Beachten Sie, dass für prime 1 zurückgegeben wird n und der größte Faktor weniger als n für Composite n kann in die Rückkehr kombiniert werden n/p wo p ist der kleinste Primfaktor von n.

(load library)               Library gives us map, -, /, min, and prime-factors functions

(lambda (L)                  Anonymous function, takes a list of numbers L
 (map                         Map
  (lambda (N)                  Anonymous function, takes a number N
   (if (less? N 2)              If N < 2
    (- 1)                        -1; else
    (/ N                         N divided by
     (min                        the minimum
      (prime-factors N)))))      of the prime factors of N
  L)))                        ... to L
DLosc
quelle