code golf - programa - Código de golf: factores primos de un número

escriba un programa que determine los factores primos de cualquier numero entero

Question

¿Cuál es el camino más corto , por número de caracteres, para encontrar factores primos en cualquier número?

Ejemplo de entrada: 1806046

Ejemplo de salida: 2x11x11x17x439

Calculadora de ejemplo

Answer 1

Javascript, 56

f="";
for(i=2;i<n;i++)
    if(n%i==0){
        f+=i+"x";
        n/=i;i--
    }
f+=n;

(54 caracteres)

Primero declare n= the number to be factored (2 caracteres incluidos)

A continuación, ejecute el código.

ejemplo:

> n=12345
  12345

> f="";for(i=2;i<n;i++)if(n%i==0){f+=i+"x";n/=i;i--}f+=n
  "3x5x823"

Answer 2

Python 3 163

Sin imprimir el resultado.

l,f,p=len,lambda n:list(filter(lambda b:n%b==0,range(2,n))),lambda n:l(f(n))==0;r=lambda n: n if p(n) else[x if p(x) else r(x) for x in [f(n)[0],f(n)[l(f(n))-1]]]

Úsalo como una función:

print(r(1806046))

Answer 3

F#

81 caracteres

let rec f n=if n=1 then[]else let a=[2..n]|>List.find(fun x->n%x=0)in a::f(n/a)

Es terriblemente ineficiente, pero dado que el objetivo es, sin duda, escribir el código más corto posible, he descuidado esa cuestión.

Forma #light (usando #light sintaxis de #light ):

let rec factorise n =
    if n = 1 then [] else
    let a = [2 .. n] |> List.find (fun x -> n % x = 0)
    a :: factorise (n / a)

Answer 4

11 caracteres en APL

Excluyendo encabezado de función y nuevas líneas

factors←{2÷/∪⌽∧/⍵∨⍳⍵}

Answer 5

En PARLANSE, esto haría el truco (252 caracteres):

(action (procedure natural)
   (loop 
      (ifthen (== ? 1) (return))
      (do f i 2 ? 1
         (ifthen (== (modulo ? i) 0)
            (print ?)
            (= ? (/ ? i))
            (exit f)
         )ifthen
      )do
    )loop
)action

Estoy seguro de que hay un programa APL mucho más pequeño para hacer esto.

Answer 6

En una vena similar a Paxinum (respuesta de Mathematica), aquí hay uno en bash:

$ factor 1806046
1806046: 2 11 11 17 439

7 caracteres el número excluyente.

Answer 7

Erlang, el núcleo es de 122 caracteres y 152 para todo el módulo:

-module(pf).
-export([f/1]).

f(N) -> f(N,2,[]).
f(1,_,L) -> lists:reverse(L);
f(N,P,L) when N rem P == 0 -> f(N div P,P,[P|L]);
f(N,P,L) -> f(N,P+1,L).

Para llamar desde la consola:

70> string:join([integer_to_list(X) || X <- pf:f(1806046)], "x").
"2x11x11x17x439"

Answer 8

La mejor respuesta de Perl hasta el momento: 70 caracteres y no hay módulos adicionales (a menos que cuente con características especiales de 5.10):

perl -nE''sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a}$,=x;say f$_''

No funciona para 1 o 0, pero funciona bien para todo lo demás. Si no te gusta usar say , o estás usando una versión anterior de Perl, aquí tienes una versión de 81 caracteres:

perl -ne''sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="/n";print f$_''

Answer 9

Mathematica (15 caracteres incluyendo paréntesis):

FactorInteger

Ejemplo:

FactorInteger[42]

{{2, 1}, {3, 1}, {7, 1}}

Answer 10

Obligatoria respuesta J (2 caracteres):

q:

Answer 11

Perl, 70 char

$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;push@x,$i}print@{$,=x}

Answer 12

Python (228 caracteres sin E / S, 340 con):

import sys

def primeFactors(n):
    l = []
    while n > 1:
        for i in xrange(2,n+1):
            if n % i == 0:
                l.append(i)
                n = n // i
                break
    return l if len(l) > 0 else [n]

n = int(sys.argv[1])
print ''%d: %s'' % (n, ''x''.join(map(lambda x: str(x), primeFactors(n))))

Se puede comprimir a 120 caracteres:

import sys
n,l=int(sys.argv[1]),[]
while n>1:
 for i in range(2,n+1):
    if n%i==0:l+=[str(i)];n/=i;break
print''x''.join(l)

Nota: Ese es un carácter de tabulación antes de if , no cuatro espacios. Funciona como otro nivel de sangría y solo cuesta un carácter en lugar de dos.

Answer 13

Si bien no es mi mejor trabajo, aquí está mi respuesta en Haskell, 83 caracteres.

f n = s [2..n] n
s [] _ = []
s (p:z) n = p:s [x | x<-z, mod x p /= 0, mod n x == 0] n

Estoy seguro de que se puede hacer más, pero por ahora es bueno.

Edición: reorganizar las cosas para afeitar un personaje, menos eficiente, pero más pequeño.

Answer 14

Solución recursiva de Python

99 caracteres (incluyendo espacios) 87 caracteres (sin espacios)

def f(n,i=2,r=""):
    while n%i<1:r+="%dx"%i;n/=i
    return f(n,i+1,r)if n>1 else r
print f(input())[:-1]

Actualización: Una versión completamente recursiva.

def f(n,i=2,x=""): return x if n<2 else f(n,i+1,x)if n%i else f(n/i,i,x+''%dx''%i)
print f(input())[:-1]

Ambas versiones son propensas a apilar desbordamientos para todas las entradas, excepto las más pequeñas.

Answer 15

Una respuesta de Mathematica que realmente produce el resultado especificado:

Print@@Riffle[Join@@ConstantArray@@@FactorInteger[n],x]

55 caracteres. Asume que n es el número de entrada x no tiene un valor asignado.

Answer 16

Wow, ustedes no son muy buenos optimizando. Puedo hacerlo en Perl en 63 caracteres, o 79 si insistes en incluir un #! / Usr / bin / perl en la parte superior:

use Math::Big::Factors;
@f=factor_wheel($ARGV[0],1);
print @f;

(No me mires de esa manera. Los programadores comprometidos son programadores perezosos ).

Answer 17

ANSI C, 79 caracteres

main(d,i){for(d+=scanf("%d",&i);i>1;i%d?++d:printf("%d%c",d,(i/=d)>1?''x'':10));}

Answer 18

C # y LINQ, 241 caracteres :

public IEnumerable<int> F(int n)
{
    return Enumerable.Range(2,n-1)
        .Where(x => (n%x)==0 && F(x).Count()==1)
        .Take(1)
        .SelectMany(x => new[]{x}.Concat(F(n/x)))
        .DefaultIfEmpty(n);
}

public string Factor(int n) {
    return F(n).Aggregate("", (s,i) => s+"x"+i).TrimStart(''x''); 
}

Comprimido:

int[] F(int n){return Enumerable.Range(2,n-1).Where(x=>(n%x)==0&&F(x).Length==1).Take(1).SelectMany(x=>new[]{x}.Concat(F(n/x))).DefaultIfEmpty(n).ToArray();}void G(int n){Console.WriteLine(F(n).Aggregate("",(s,i)=>s+"x"+i).TrimStart(''x''));}

Answer 19

C #, 366 caracteres

C # no es el lenguaje más promedio para algo como esto, pero esto es bastante compacto:

class P {
   static void Main(string[] a) {
      int i = int.Parse(a[0]);
      var p = new System.Collections.Generic.List<int>();
      for (int n = 2; i > 1; n++)
         if (p.Find(q => n % q == 0) == 0) {
            p.Add(n);
            while (i % n == 0) {
               System.Console.WriteLine(n);
               i /= n;
            }
         }
   }
}

Editar:
Vi que Noldorin usaba el método List.Find en su código F #, y me di cuenta de que sería un poco más corto que un foreach ...

Editar:
Bueno, si no tiene que ser un programa completo ...

C #, 181 caracteres

string f(int i) {
   var r = "";
   var p = new System.Collections.Generic.List<int>();
   for (int n = 2; i > 1; n++)
      if (p.Find(q => n % q == 0) == 0) {
         p.Add(n);
         while (i % n == 0) {
            r += "x" + n;
            i /= n;
         }
      }
   return r.Substring(1);
}

Comprimido:

string f(int i){var r="";var p=new System.Collections.Generic.List<int>();for(int n=2;i>1;n++)if(p.Find(q=>n%q==0)==0){p.Add(n);while(i%n==0){r+="x"+n;i/=n;}}return r.Substring(1);}

Answer 20

C #, 69

x es el número de entrada

int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};

Con incluye:

using system;
namespace nameSP
{
   class Program
   {
     static void Main(string[] args)
     { 
        int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};
     }
   }
}

Answer 21

El lenguaje de programación Go, 100 caracteres:

package main;func main(){n:=42;c:="x";for i:=2;n>1;i++{if n%i<1{n/=i;if(n<2){c=""};print(i,c);i--}}}

Mi programa, con la sangría correcta:

package main

func main() {
 n := 42 // or whichever input number you like
 c := "x" // separating printed integers
 for i:=2 ; n>1; i++ {
  if n%i<1 { // n%i==0
   n /= i
   if(n<2) { c = "" } // n==1
   print(i, c)
   i--
  }
 }
}

Answer 22

Euforia: 106 caracteres

procedure f(atom a)atom x=2
loop do
while remainder(a,x)do
x+=1
end while
?x
a/=x
until a=1
end procedure

Answer 23

GNU bc , 47 caracteres, incluida la recopilación de datos (necesita las extensiones GNU para print , y read ):

x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;i}

Si realmente quieres los caracteres x en la salida, son 64 caracteres:

x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;print i;if(x>1)"x"}

Además, tenga en cuenta que el uso de bc permite que esto procese números de longitud arbitraria.

Answer 24

Haskell, 53 caracteres: (incluidas 3 nuevas líneas)

a%1=[]
a%n|mod n a<1=a:p(div n a)|1>0=(a+1)%n
p=(2%)

Ejemplo:

*Main> p 1806046
[2,11,11,17,439]

Answer 25

Perl, 223 caracteres

perl -ne''f($o=$_,2);sub f{($v,$f)=@_;$d=$v/$f;if(!($d-int($d))){print"$f ";if(!p($d)){print"$d ";return(0);}else{f($d,$f);}}else{while(p(++$f)){}f($v,$f);}}sub p{for($i=2;$i<=sqrt($_[0]);$i++){if($_[0]%$i==0){return(1);}}}''

Answer 26

Python: 77 caracteres con entrada y salida.

d,s,n=2,'''',input()
while n>1:
 if n%d:d+=1
 else:s+=''%dx''%d;n/=d
print s[:-1]

Answer 27

Rubí 39B 71B (a través de STDIN)

#!ruby -nrmathn
p$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"

Answer 28

VB6 / VBA - 147 caracteres

No se me permite dejar comentarios, pero es posible acortar un poco la respuesta anterior al no tener Option Explicit . Aprovechando algunas de las características más peligrosas de VB6 / VBA, puede utilizar la siguiente. ¡No es necesario declarar cuál es la variable y la función tampoco tiene que ser declarada pública si va por falta definitiva! También el Fin Si no es necesario si está en la misma línea.

Function P(N As Long)
    Dim I, O
    Do While N > 1: For I = 2 To N
    If N Mod I = 0 Then O = O & " " & I: N = N / I: Exit For: 
    Next: Loop: P = O
End Function

Esto puede ser probado por:

Public Sub TestP()
    Dim s: s = P(1806046)
    Debug.Print s
End Sub

Answer 29

VB6 / VBA - 190 caracteres

Public Function P(N As Long) As String
Dim I As Long, O As String
Do While N > 1: For I = 2 To N
If N Mod I = 0 Then
O = O & " " & I: N = N / I: Exit For: End If: Next: Loop: P = O: End Function

Answer 30

74 75 personajes en Python

a=input();b=2
while b*b<=a:
    if a%b==0:print b;a/=b;b=1
    b+=1
print a

Derivado de mi código TI-BASIC para la factorización prima.

Ya que estoy hablando de TI-Basic ...

77 personajes en TI-Basic

input a
2→b
while b²<a
a/b→c
if int(c)=c:then:disp b:c→a:1→b:end
b+1→b
end
disp a