Oblicz czynniki pierwsze

27

Jakiś czas temu mieliśmy poważne wyzwanie faktoryzacji , ale to wyzwanie ma prawie sześć lat i ledwo spełnia nasze obecne wymagania, więc uważam, że nadszedł czas na nowe.

Wyzwanie

Napisz program lub funkcję, która przyjmuje na wejściu liczbę całkowitą większą niż 1 i wyświetla lub zwraca listę swoich czynników pierwszych.

Zasady

  • Dane wejściowe i wyjściowe można podawać dowolną standardową metodą i w dowolnym standardowym formacie.
  • Dane wyjściowe muszą zawierać zduplikowane czynniki.
  • Dane wyjściowe mogą być w dowolnej kolejności.
  • Wartość wejściowa nie będzie mniejsza niż 2 lub większa niż 2 31-1 .
  • Wbudowane są dozwolone, ale zalecane jest włączenie rozwiązania niewbudowanego.

Przypadki testowe

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

Punktacja

To jest , więc wygrywa najkrótszy kod w bajtach.

ETHprodukcje
źródło
2
Byłoby znacznie lepiej, gdybyś zabronił wbudowanych.
Bufor
2
@ Wyzwania TheBitByte, które uniemożliwiają wbudowanie, są ogólnie traktowane jako Do X bez wyzwań Y , szczególnie, że czasami trudno jest stwierdzić, czy rozwiązanie jest technicznie wbudowane.
ETHproductions
1
Ciesz się więc napływem rozwiązań <5 bajtów! Kiedy to piszę, Pyth robi to już w 1 bajcie.
Bufor
2
@TheBitByte Uważaj to przede wszystkim za wyzwanie dla poszczególnych języków. Spróbuj pokonać rozwiązanie Pythona lub inny język bez wbudowanego.
isaacg
1
@isaacg Cóż, język po języku to lepszy sposób patrzenia na to, zgadzam się.
Bufor przed

Odpowiedzi:

15

Pyth , 1 bajt

P

Lubię szanse Pytha w tym wyzwaniu.

isaacg
źródło
16
Do momentu
pojawienia się
13

Python 2 , 55 bajtów

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

Wypróbuj online!

Dennis
źródło
1
Założę się, że czekałeś to przez większość godziny ...
ETHproductions
10

Python 2, 53 bajty

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

Próbuje kolejno każdego potencjalnego dzielnika i. Jeśli ijest dzielnikiem, wstawi go i uruchomi ponownie n/i. W przeciwnym razie próbuje następnego najwyższego dzielnika. Ponieważ dzielniki są sprawdzane w kolejności rosnącej, znaleziono tylko te pierwsze.

Jako program dla 55 bajtów:

n=input();i=2
while~-n:
 if n%i:i+=1
 else:n/=i;print i
xnor
źródło
8

Mathematica, 38 30 bajtów

Dzięki @MartinEnder za 8 bajtów!

Join@@Table@@@FactorInteger@#&
JungHwan Min
źródło
Jak o FactorInteger[#][[All, 1]]&? 26 bajtów
David G. Stork
@ DavidG.Stork, który nie zadziałałby, ponieważ nie powtórzyłby głównych czynników, gdyby moc była większa niż 1.
JungHwan Min
5

Haskell , 48 bajtów

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

Wypróbuj online! Przykładowe użycie: (2%) 1001daje [7,11,13].

Laikoni
źródło
4

JavaScript (ES6), 44 bajty

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

Strasznie nieefektywny ze względu na to, że iteruje od 2 do każdego czynnika pierwszego, w tym ostatniego. Możesz znacznie zmniejszyć złożoność czasu kosztem 5 bajtów:

f=(n,x=2)=>x*x>n?[n]:n%x?f(n,x+1):[x,...f(n/x,x)]
ETHprodukcje
źródło
3

Właściwie 6 bajtów

w`in`M

Wypróbuj online!

Wyjaśnienie:

w`in`M
w       factor into primes and exponents
 `in`M  repeat each prime # of times equal to exponent
Mego
źródło
Prawdopodobnie możesz po prostu użyć oteraz, prawda?
Oliver,
@Oliver Tak, ale zwykle nie aktualizuję starych odpowiedzi za pomocą wbudowanych funkcji.
Mego
3

J, 2 bajty

q:

Treść musi mieć co najmniej 30 znaków.

alephalpha
źródło
3

Japt, 2 bajty

Uk

Wbudowane kużywane na wejściu U. Odnosi się także do kraju.

Przetestuj online!

ETHprodukcje
źródło
2

tonowo głuchy , 3 bajty

Ten język jest dość młody i nie jest jeszcze naprawdę gotowy na nic ważnego, ale potrafi dokonać podstawowej faktoryzacji:

A/D

Będzie to czekać na dane wejściowe użytkownika, a następnie wyświetli listę głównych czynników.

Kade
źródło
2

MATLAB, 6 bajtów

Myślę, że nie wymaga to żadnego wyjaśnienia.

factor
wada
źródło
1

Bash + coreutils, 19 bajtów

factor|sed s/.*:.//

Wypróbuj online!

Dennis
źródło
Możesz zgolić bajt, jeśli białe znaki nie mają znaczenia na wyjściu przy użyciu factor|sed s/.*://. Również factor|cut -d: -f2(lub w factor|cut -d\ -f2celu dopasowania do bieżącego wyniku) ma tę samą długość bajtu, ale będzie działać szybciej i zużywać mniej pamięci.
Caleb,
Zapytam OP o białe znaki. Niestety musiałbym factor|cut -d\ -f2-wyeliminować wiodącą przestrzeń, która jest o jeden bajt dłużej.
Dennis
1

Partia, 96 bajtów

@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
źródło
1

Sześciokąty , 58 bajtów

Nie skończyłem jeszcze gry w golfa, ale @MartinEnder i tak powinien być w stanie to zniszczyć

Drukuje czynniki oddzielone spacjami, z końcową spacją

Gra w golfa:

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

Wyłożony:

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

Wyjaśnienie nastąpi później.

niebieski
źródło
1

CJam, 2 bajty

mf

cjam.aditsu.net / ...

To jest funkcja. Martin, wygląda na to, że byłem śpiący.

Erik the Outgolfer
źródło
1

C, 92 bajty

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);}

Wersja bez golfa:

#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
źródło
0

Perl 6 , 77 64 bajtów  

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

Spróbuj

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

Wypróbuj (Uwaga: nie ma wystarczająco dużo czasu na ukończenie)


Znacznie bardziej wydajna wersja jest nieco dłuższa przy 100 bajtach.

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

Spróbuj


Rozszerzony: (wersja 64-bajtowa)

{
  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
źródło
0

VB.NET, 86 bajtów

Miałem to z niektórych programów Project Euler. Usunięto optymalizacje w interesie krótkości, a to jest wynik. Oczywiście VB jest bardzo gadatliwy, więc jest dość długi. Nie liczę wiodących białych znaków. Można go pominąć, ale łatwiej go odczytać.

Pobiera to liczbę całkowitą jako parametr i wypisuje czynniki pierwsze przecinkiem po. Na końcu znajduje się przecinek.

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.
źródło
0

Perl 6 , 51 bajtów

Rozwiązanie rekurencyjne:

sub f(\n,\d=2){n-1??n%d??f n,d+1!!(d,|f n/d,d)!!()}
Sean
źródło
0

Java (OpenJDK) , 259 bajtów

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?", ":""));}}

Wypróbuj online!

Pavel
źródło
Zapoznaj się z tą treścią, aby zobaczyć, w jaki sposób można dalej grać w golfa: gist.github.com/kritixilithos/fde37dc5a8ae54852aa134a6e70ea495 . Jeśli chcesz coś wyjaśnić, możesz
wysłać
0

Rubin, 61 bajtów

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

Najkrótsza wbudowana wersja, o której mogłem myśleć.

Seims
źródło