Wir hatten vor einiger Zeit eine primäre Faktorisierungsherausforderung , aber diese Herausforderung ist fast sechs Jahre alt und entspricht kaum unseren aktuellen Anforderungen. Ich glaube, es ist Zeit für eine neue.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine ganze Zahl größer als 1 als Eingabe verwendet und eine Liste ihrer Primfaktoren ausgibt oder zurückgibt.

Regeln

Die Ein- und Ausgabe kann nach einer beliebigen Standardmethode und in einem beliebigen Standardformat erfolgen.
Doppelte Faktoren müssen in der Ausgabe enthalten sein.
Die Ausgabe kann in beliebiger Reihenfolge erfolgen.
Die Eingabe wird nicht kleiner als 2 oder größer als 2 ³¹ - 1 sein.
Built-Ins sind erlaubt, aber auch eine nicht eingebaute Lösung wird empfohlen.

Testfälle

2 -> 2
3 -> 3
4 -> 2, 2
6 -> 2, 3
8 -> 2, 2, 2
12 -> 2, 2, 3
255 -> 3, 5, 17
256 -> 2, 2, 2, 2, 2, 2, 2, 2
1001 -> 7, 11, 13
223092870 -> 2, 3, 5, 7, 11, 13, 17, 19, 23
2147483646 -> 2, 3, 3, 7, 11, 31, 151, 331
2147483647 -> 2147483647

Wertung

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

code-golf primes factoring ETHproductions
quelle

2

Wäre viel besser gewesen, wenn Sie Einbauten nicht zugelassen hätten.

Buffer Over Read

2

@TheBitByte Herausforderungen, die eingebaute Komponenten nicht zulassen, werden im Allgemeinen als Do X ohne Y- Herausforderungen betrachtet, zumal es manchmal schwierig ist, zu erkennen, ob eine Lösung technisch eine eingebaute Lösung ist.

ETHproductions

1

Dann genießen Sie den Zufluss von <5-Byte-Lösungen! Während ich das schreibe, macht Pyth das schon in 1 Byte.

Buffer Over Read

2

@TheBitByte Betrachten Sie es in erster Linie als sprachspezifische Herausforderung. Versuchen Sie, Pythons Lösung oder eine andere Sprache ohne eingebauten Code zu schlagen.

Isaacg

1

@isaacg Nun, Sprache für Sprache ist eine bessere Sichtweise, da stimme ich zu.

Buffer Over Read

15

Pyth , 1 Byte

Ich mag Pyths Chancen bei dieser Herausforderung.

isaacg
quelle

16

Bis die "P" -Sprache kommt und es in 0 Bytes

tut

13

Python 2 , 55 Bytes

f=lambda n,k=2:n/k*[0]and(f(n,k+1),[k]+f(n/k,k))[n%k<1]

Probieren Sie es online!

Dennis
quelle

1

Ich wette, Sie haben die meiste Stunde darauf gewartet ...

ETHproductions

10

Python 2, 53 Bytes

f=lambda n,i=2:n/i*[f]and[f(n,i+1),[i]+f(n/i)][n%i<1]

Versucht jeden möglichen Teiler i . Wenn ies sich um einen Divisor handelt, wird dieser vorangestellt und mit neu gestartet n/i. Andernfalls wird der nächsthöhere Divisor ausprobiert. Da die Teiler in aufsteigender Reihenfolge geprüft werden, werden nur die Primzahlen gefunden.

Als Programm für 55 Bytes:

n=input();i=2
while~-n:
 if n%i:i+=1
 else:n/=i;print i

xnor
quelle

8

Mathematica, 38 30 Bytes

Danke @MartinEnder für 8 Bytes!

Join@@Table@@@FactorInteger@#&

JungHwan min
quelle

Wie wäre es FactorInteger[#][[All, 1]]&? 26 Bytes

David G. Stork

@ DavidG.Stork, das würde nicht funktionieren, weil es die Primfaktoren nicht wiederholen würde, wenn die Leistung größer als 1 ist.

JungHwan Min

5

Gelee , 2 Bytes

Æf

Probieren Sie es online!

Dennis
quelle

5

Haskell , 48 Bytes

(2%)
n%1=[]
n%m|mod m n<1=n:n%div m n|k<-n+1=k%m

Probieren Sie es online! Anwendungsbeispiel: (2%) 1001Erträge [7,11,13].

Laikoni
quelle

4

JavaScript (ES6), 44 Byte

f=(n,x=2)=>n-1?n%x?f(n,x+1):[x,...f(n/x)]:[]

Schrecklich ineffizient, da es von 2 bis zu jedem Primfaktor, einschließlich des letzten, iteriert. Sie können die Zeitkomplexität auf Kosten von 5 Byte drastisch reduzieren:

f=(n,x=2)=>x*x>n?[n]:n%x?f(n,x+1):[x,...f(n/x,x)]

ETHproductions
quelle

4

Cubix , 37 32 Bytes

vs(...<..1I>(!@)s)%?w;O,s(No;^;<

Probieren Sie es online! oder Beobachten Sie es in Aktion .

ETHproductions
quelle

3

Eigentlich 6 Bytes

w`in`M

Probieren Sie es online!

Erläuterung:

w`in`M
w       factor into primes and exponents
 `in`M  repeat each prime # of times equal to exponent

Mego
quelle

Sie können wahrscheinlich nur ojetzt verwenden, oder?

Oliver

@Oliver Ja, aber ich aktualisiere in der Regel keine alten Antworten mit integrierten Funktionen.

Mego

3

J, 2 Bytes

q:

~~Body muss mindestens 30 Zeichen lang sein.~~

Alephalpha
quelle

3

MATL , 2 Bytes

Yf

Probieren Sie es online!

Obligatorische "langweilige Antwort".

DJMcMayhem
quelle

3

Japt, 2 Bytes

Uk

Ein kfür den Eingang verwendetes eingebautes Gerät U. Bezieht sich auch auf ein Land.

Online testen!

ETHproductions
quelle

2

taub , 3 Bytes

Diese Sprache ist noch recht jung und noch nicht wirklich bereit für irgendetwas Wesentliches, kann aber Primfaktorisierung leisten:

A/D

Dies wartet auf Benutzereingaben und gibt dann die Liste der Primfaktoren aus.

Kade
quelle

2

MATLAB, 6 Bytes

Ich denke, das bedarf keiner Erklärung.

factor

Fehler
quelle

1

Bash + Coreutils, 19 Bytes

factor|sed s/.*:.//

Probieren Sie es online!

Dennis
quelle

Sie können ein Byte abschneiden, wenn Whitespace in der Ausgabe mit keine Rolle spielt factor|sed s/.*://. Außerdem factor|cut -d: -f2(oder factor|cut -d\ -f2entsprechend Ihrer aktuellen Ausgabe) hat es die gleiche Bytelänge, wird jedoch schneller ausgeführt und benötigt weniger Speicherplatz.

Caleb

Ich werde das OP nach Whitespace fragen. Leider müsste ich factor|cut -d\ -f2-den führenden Bereich entfernen, der ein Byte länger ist.

Dennis

1

Batch, 96 Bytes

@set/an=%1,f=2,r=0
:l
@set/af+=!!r,r=n%%f
@if %r%==0 echo %f%&set/an/=f
@if %n% gtr 1 goto l

Neil
quelle

1

Pyke, 1 Byte

Probieren Sie es hier aus!

Primfaktoren eingebaut.

Blau
quelle

1

Hexagonie , 58 Bytes

Noch nicht golfen, aber @MartinEnder sollte das sowieso zerstören können

Gibt die Faktoren mit einem Leerzeichen am Ende durch Leerzeichen getrennt aus

Golf gespielt:

2}\..}$?i6;>(<...=.\'/})."@...>%<..'':\}$"!>~\{=\)=\}&<.\\

Ausgelegt:

     2 } \ . .
    } $ ? i 6 ;
   > ( < . . . =
  . \ ' / } ) . "
 @ . . . > % < . .
  ' ' : \ } $ " !
   > ~ \ { = \ )
    = \ } & < .
     \ \ . . .

Erklärung kommt später.

Blau
quelle

1

05AB1E , 1 Byte

Ò

Probieren Sie es online!

Erik der Outgolfer
quelle

1

Ich frage mich, wie viele Leute Dennis outgolfen werden ...

Erik the Outgolfer

1

CJam, 2 Bytes

mf

cjam.aditsu.net / ...

Dies ist eine Funktion. Martin, ich war anscheinend müde.

Erik der Outgolfer
quelle

1

C 92 Bytes

int p(int n){for(int i=2;i<n;i++)if(n%i==0)return printf("%d, ",i)+p(n/i);printf("%d\n",n);}

Ungolfed-Version:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int prime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            printf("%d, ", i);
            return prime(number / i); //you can golf away a few bytes by returning the sum of your recursive function and the return of printf, which is an int
        }                             //this allow you to golf a few more bytes thanks to inline calls
    }
    printf("%d\n", number);
}

int main(int argc, char **argv) {
    prime(atoi(argv[1]));
}

Valentin Mariette
quelle

1

Japt , 1 Byte (nicht konkurrierend)

Probieren Sie es online!

Oliver
quelle

1

PHP , 51 Bytes

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i*print"$i ";

Probieren Sie es online!

Jörg Hülsermann
quelle

1

C (gcc) , 51 Bytes

i;f(n){for(i=2;i<=n;)n%i?i++:printf("%d ",i,n/=i);}

Probieren Sie es online!

Gastropner
quelle

0

Perl 6 , 77 64 Bytes

{my$a=$_;.is-prime??$_!!map ->\f{|({$a%f||($a/=f)&&f}...^*!= f)},(2... *>$a)}

Versuch es

{my$a=$_;map ->\f{|({$a%f||($a div=f)&&f}...^ f>*)},(2... *>$a)}

Versuch es (Hinweis: Es ist nicht genügend Zeit für die Fertigstellung vorgesehen.)

Eine viel performantere Version ist mit 100 Bytes etwas länger.

{my$a=$_;map ->\f{|({$a.is-prime??($/=$a)&&($a=0)||$/!!($a%f||($a div=f)&&f)}...^ f>*)},(2... *>$a)}

Versuch es

Erweitert: ^{_{(64-Byte-Version)}}

{
  my $a = $_;  # the input ｢$_｣ is read-only by default
  map
    -> \f {
      |(              # slip ( flattens into outer list )

        # generate sequence of 0 or more ｢f｣s
        {
          $a % f      # is it not evenly divisible

          ||          # if it is evenly divisible
          ($a div=f)  # divide it
          &&          # and
          f           # return ｢f｣
        }
        ...^   # keep doing that until
        f > *  # ｢f｣ is bigger
      )

    },

    # do that over the following list

    (2 ... * > $a) # generate a sequence from 2
                   # up to whatever the value of $a
                   # is at the time of the check
}

Brad Gilbert b2gills
quelle

0

VB.NET, 86 Bytes

Hatte dies aus einigen Project-Euler-Programmen rumgesessen. Die Optimierungen wurden aus Gründen der Kürze entfernt, und dies ist das Ergebnis. Natürlich ist VB sehr ausführlich, es ist also ziemlich lang. Ich zähle nicht das führende Leerzeichen. Es kann weggelassen werden, ist aber einfacher damit zu lesen.

Dies nimmt eine ganze Zahl als Parameter und gibt die Primfaktoren mit einem Komma danach aus. Am Ende steht ein Nachkomma.

Sub A(a)
    For i=2To a ' VB re-evaluates a each time, so the /= at the end of the loop shortens this
        While a Mod i=0 ' this is a factor. We've grabbed primes before this, so this must be a prime factor
            Console.Write(i &",") ' output
            a/=i ' "mark" the prime as "used"
        End While
    Next
End Sub

Brian J
quelle

0

Perl 6 , 51 Bytes

Eine rekursive Lösung:

sub f(\n,\d=2){n-1??n%d??f n,d+1!!(d,|f n/d,d)!!()}

Sean
quelle

0

Java (OpenJDK) , 259 Byte

import java.util.*;interface g{static void main(String[]z){int a=new Scanner(System.in).nextInt();int b=0;int[]l={};for(int i=2;i<=a;i++){for(;a%i<1;l[b-1]=i){l=Arrays.copyOf(l,b=l.length+1);a/=i;}}for(int i=0;i<b;i++)System.out.print(l[i]+(i<b-1?", ":""));}}

Probieren Sie es online!

Pavel
quelle

In diesem Artikel erfahren Sie, wie Sie mit diesem Beitrag weiter Golf spielen können: gist.github.com/kritixilithos/fde37dc5a8ae54852aa134a6e70ea495 . Wenn Sie etwas klären müssen, können Sie mich

gerne

0

Ruby, 61 Bytes

require'prime';->x{x.prime_division.flat_map{|x|[x[0]]*x[1]}}

Kürzeste eingebaute Version, die mir in den Sinn kam.

Seims
quelle

0

Ruby , 48 Bytes

->x{r,*c=2;0while(x%r<1?(x/=r)&&c<<r:x>=r+=1);c}

Probieren Sie es online!

Ein bisschen zu spät zur Party, aber ... warum nicht?

GB
quelle

Berechnen Sie die Primfaktoren

Herausforderung

Regeln

Testfälle

Wertung

Antworten:

Pyth , 1 Byte

Python 2 , 55 Bytes

Python 2, 53 Bytes

Mathematica, 38 30 Bytes

Gelee , 2 Bytes

Haskell , 48 Bytes

JavaScript (ES6), 44 Byte

Cubix , 37 32 Bytes

Eigentlich 6 Bytes

J, 2 Bytes

MATL , 2 Bytes

Japt, 2 Bytes

taub , 3 Bytes

MATLAB, 6 Bytes

Bash + Coreutils, 19 Bytes

Batch, 96 Bytes

Pyke, 1 Byte

Hexagonie , 58 Bytes

05AB1E , 1 Byte

CJam, 2 Bytes

C 92 Bytes

Japt , 1 Byte (nicht konkurrierend)

PHP , 51 Bytes

C (gcc) , 51 Bytes

Perl 6 , 77 64 Bytes

Erweitert: ^{_{(64-Byte-Version)}}

VB.NET, 86 Bytes

Perl 6 , 51 Bytes

Java (OpenJDK) , 259 Byte

Ruby, 61 Bytes

Ruby , 48 Bytes

Berechnen Sie die Primfaktoren

Herausforderung

Regeln

Testfälle

Wertung

Antworten:

Pyth , 1 Byte

Python 2 , 55 Bytes

Python 2, 53 Bytes

Mathematica, 38 30 Bytes

Gelee , 2 Bytes

Haskell , 48 Bytes

JavaScript (ES6), 44 Byte

Cubix , 37 32 Bytes

Eigentlich 6 Bytes

J, 2 Bytes

MATL , 2 Bytes

Japt, 2 Bytes

taub , 3 Bytes

MATLAB, 6 Bytes

Bash + Coreutils, 19 Bytes

Batch, 96 Bytes

Pyke, 1 Byte

Hexagonie , 58 Bytes

05AB1E , 1 Byte

CJam, 2 Bytes

C 92 Bytes

Japt , 1 Byte (nicht konkurrierend)

PHP , 51 Bytes

C (gcc) , 51 Bytes

Perl 6 , 77 64 Bytes

Erweitert: (64-Byte-Version)

VB.NET, 86 Bytes

Perl 6 , 51 Bytes

Java (OpenJDK) , 259 Byte

Ruby, 61 Bytes

Ruby , 48 Bytes

Erweitert: ^{_{(64-Byte-Version)}}