Factorización de 2 factores

14

Dado un número natural, nescriba un programa o función para obtener una lista de todas las multiplicaciones posibles de dos factores que se pueden usar para lograr n. Para entender mejor lo que se pretende se puede ir a http://factornumber.com/?page=16777216 para ver cuando nes 16777216que obtenemos la siguiente lista:

   2 × 8388608  
   4 × 4194304  
   8 × 2097152  
  16 × 1048576  
  32 ×  524288  
  64 ×  262144  
 128 ×  131072  
 256 ×   65536  
 512 ×   32768  
1024 ×   16384
2048 ×    8192
4096 ×    4096

No es necesario imprimir cosas bonitas como aquí. El requisito es que cada entrada (par de factores) se distinga bien entre sí y dentro de cada par, el primer factor también se distingue bien del otro. Si elige devolver una lista / matriz, el elemento interno puede ser una lista / matriz con dos elementos, o alguna estructura de su lenguaje que admita un par de cosas como C ++ std::pair.

No imprima la multiplicación por 1 entrada, ni repita las entradas con el primer factor conmutado por el segundo, ya que son bastante inútiles.

Sin ganador; será un código de golf por idioma.

sergiol
fuente
2
¿Podría agregar un caso de prueba más pequeño, como 30?
caird coinheringaahing
1
@cairdcoinheringaahing Puede usar factornumber.com para generar más casos de prueba.
Jonathan Frech
1
He visto esta competencia "por idioma" recientemente. ¿Cuál es el punto de? La mayoría de las Q no obtienen más de 1 o 2 según el idioma, y ​​aún puede seleccionar solo una A como correcta.
fede s.
55
@fedes. Por lo general, es porque no tiene sentido comparar idiomas (es decir, Java vs. Jelly).
Totalmente humano el
1
@totallyhuman sí, lo sé. La mayoría de mis respuestas están en Factor, o incluso Smalltalk. No hay posibilidad contra los idiomas de golf. Tal vez podría haber alguna forma de clasificar los idiomas por verbosidad y calderería
fede s.

Respuestas:

6

Java (OpenJDK 8) , 81 66 65 bytes

  • -15 Bytes gracias a Olivier Grégoire.
  • -1 Byte: ++j<=i/j-> j++<i/j.
i->{for(int j=1;j++<i/j;)if(i%j<1)System.out.println(j+" "+i/j);}

Pruébalo en línea!


Viejo (para referencia)

Java (OpenJDK 8) , 126 bytes

i->{java.util.stream.IntStream.range(2,i).filter(d->d<=i/d&&i%d==0).forEach(e->System.out.println(""+e+"x"+i/e));return null;}

Pruébalo en línea!

Primer envío de codegolf y primer uso de lambda. Yo futuro, perdóname por el código.

Bernat
fuente
1
Bonita primera entrada! Bienvenido a PPCG! Aquí se redujo a 66 bytes eliminando todo lo superfluo: aunque no pude jugar a su algoritmo.
Olivier Grégoire
5

05AB1E , 8 bytes

Ñ‚ø2äн¦

Pruébalo en línea!

Emigna
fuente
2
De mi parte, tenemos casi las mismas soluciones. Pensé en este 8 byter
Sr. Xcoder,
@ Mr.Xcoder: Ah sí, agradable :) Es una pena que el mapa se requiera allí.
Emigna
5

Python 2 , 51 bytes

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

Pruébalo en línea!


51 bytes (gracias a Luis Mendo por un byte)

lambda n:[(n/k,k)for k in range(1,n)if(k*k<=n)>n%k]

Pruébalo en línea!


51 bytes

lambda n:[(n/k,k)for k in range(1,n)if n/k/k>n%k*n]

Pruébalo en línea!

xnor
fuente
Me gusta el uso de [f].
Jonathan Frech
1
Puede guardar 1 byte en la segunda versión conlambda n:[(n/k,k)for k in range(1,n)if(k*k<=n)>n%k]
Luis Mendo
MemoryError en todos los enfoques para 1512518520
sergiol
4

Haskell, 38 bytes

f x=[(a,b)|a<-[2..x],b<-[2..a],a*b==x]

Pruébalo en línea!

nimi
fuente
Tiempo de espera para 1512518520
sergiol
3

Perl 6 , 38 bytes

{map {$^a,$_/$a},grep $_%%*,2.. .sqrt}

Intentalo

Expandido:

{   # bare block lambda with implicit parameter 「$_」

  map
    { $^a, $_ / $a },  # map the number with the other factor

    grep
      $_ %% *,         # is the input divisible by *
      2 .. .sqrt       # from 2 to the square root of the input
}
Brad Gilbert b2gills
fuente
3

Brachylog , 8 bytes

{~×≜Ċo}ᵘ

Pruébalo en línea!

Explicación

{~×≜Ċo}ᵘ
{     }ᵘ  List the unique outputs of this predicate.
 ~×       Pick a list of integers whose product is the input.
   ≜      Force concrete values for its elements.
    Ċ     Force its length to be 2.
     o    Sort it and output the result.

La parte no incluye 1s en su salida, por lo que para la entrada N da [N] en lugar de [1, N] , que luego se selecciona Ċ. No estoy completamente seguro de por qué es necesario ...

Zgarb
fuente
1
El es necesaria porque de lo contrario no hay puntos de elección para : una lista de longitud-2 cuyo producto es la entrada es la única respuesta si en realidad no solicita los valores de la lista.
Fatalize
2

Japt , 9 bytes

â¬Å£[XZo]

¡Pruébalo en línea! Devuelve una matriz de matrices, con algunos nulos al final; -Rbandera agregada para mostrar la salida más claramente.

ETHproductions
fuente
1
Así que creo que el `-R` debería considerarse para el recuento de bytes ...
sergiol
3
@sergiol, no, en este caso es solo para formatear la salida para una mejor legibilidad.
Shaggy
Exactamente la solución que tenía, excepto que filtré el nulls al final.
Shaggy
2

Jalea , 8 bytes

½ḊpP⁼¥Ðf

Un enlace monádico que toma un número y devuelve una lista de listas (pares) de números.

Pruébalo en línea! (se agota el tiempo de espera de TIO para el16777216ejemplo, ya que crearía una lista de 68.7 mil millones de pares y se filtraría a aquellos con el producto correcto)

¿Cómo?

½ḊpP⁼¥Ðf - Link: number, n     e.g. 144
½        - square root of n          12
 Ḋ       - dequeue*                 [2,3,4,5,6,7,8,9,10,11,12]
  p      - Cartesian product**      [[2,1],[2,2],...[2,144],[3,1],...,[3,144],...,[12,144]
      Ðf - filter keep if:
     ¥   -   last two links as a dyad (n is on the right):
   P     -     product
    ⁼    -     equals
         -                          [[2,72],[3,48],[4,36],[6,24],[8,18],[9,16],[12,12]]

* , dequeue, hace implícitamente un rango de una entrada numérica antes de actuar, y la función de rango pone implícitamente su entrada, por lo que, por ejemplo, con n=24el resultado de ½es 4.898...; el rango se vuelve [1,2,3,4]; y el resultado retrasado es[2,3,4]

** De manera similar a lo anterior, el pproducto cartesiano crea rangos para la entrada numérica; aquí, el argumento correcto es, npor lo tanto, el argumento correcto se convierte en [1,2,3,...,n]anterior a que tenga lugar el producto cartisiano real.

Jonathan Allan
fuente
2

Casco , 8 bytes

tüOSze↔Ḋ

Pruébalo en línea!

Explicación

tüOSze↔Ḋ  Implicit input, say n=30.
       Ḋ  List of divisors: [1,2,3,5,6,10,15,30]
      ↔   Reverse: [30,15,10,6,5,3,2,1]
   Sze    Zip with original: [[1,30],[2,15],[3,10],[5,6],[6,5],[10,3],[15,2],[30,1]]
 üO       Deduplicate by sort: [[1,30],[2,15],[3,10],[5,6]]
t         Drop first pair: [[2,15],[3,10],[5,6]]
Zgarb
fuente
2

JavaScript (ES6), 55 bytes

n=>eval('for(k=1,a=[];k*++k<n;n%k||a.push([k,n/k]));a')

Manifestación

¡Pruébelo en línea!

Arnauld
fuente
¿Soy yo o esto falla 6?
Neil
@Neil "Podemos arreglarlo". (¡Gracias por informar!)
Arnauld
¿Cómo puedo proporcionar un número para probar?
sergiol
¡Puedes probarlo en línea!
Arnauld
1

Python 2 , 59 bytes

lambda N:{(n,N/n,n)[n>N/n:][:2]for n in range(2,N)if N%n<1}

Pruébalo en línea!

Jonathan Frech
fuente
@sergiol Sí, un MemoryError, ya que Python intenta evaluarlo range(2,N)y almacenarlo como una lista, pero la memoria asignada no es suficiente. Uno podría intentar reemplazar rangecon xrange(generador de rango de Python 2), aunque esto excede el minuto de tiempo de ejecución máximo de TIO. En una máquina con suficiente memoria y tiempo, este programa debe finalizar y devolver la respuesta correcta.
Jonathan Frech
1

PHP, 70 bytes

Como cadena (70 bytes):

$i++;while($i++<sqrt($a=$argv[1])){echo !($a%$i)?" {$i}x".($a/$i):'';}

Como volcado de matriz (71 bytes):

$i++;while($i++<sqrt($a=$argv[1]))!($a%$i)?$b[$i]=$a/$i:'';print_r($b);

(No estoy seguro de si puedo usar return $ b; en lugar de print_r ya que ya no genera la matriz, de lo contrario, puedo guardar 2 bytes aquí).

La matriz da los resultados como:

Array
(
    [2] => 8388608
    [4] => 4194304
    [8] => 2097152
    [16] => 1048576
RFSnake
fuente
"Si elige devolver una lista / matriz" Para mí significa que puede imprimir o regresar como mejor le parezca.
fede s.
Pensándolo bien, regresar debería ser válido para una función e imprimir para un programa. Parece que tiene un fragmento / programa, no una función, por lo que en este caso debería decir que debería imprimir.
fede s.
1

Jalea , 12 bytes

ÆDµżUḣLHĊ$$Ḋ

Pruébalo en línea!

Cómo funciona

ÆDµżUḣLHĊ$$Ḋ - Main monadic link;
             - Argument: n (integer) e.g. 30
ÆD           - Divisors                   [1, 2, 3, 5, 6, 10, 15, 30]
    U        - Reverse                    [30, 15, 10, 6, 5, 3, 2, 1]
   ż         - Interleave                 [[1, 30], [2, 15], [3, 10], [5, 6], [6, 5], [10, 3], [15, 2], [30, 1]]
         $$  - Last 3 links as a monad
      L      -   Length                   8
       H     -   Halve                    4
        Ċ    -   Ceiling                  4
     ḣ       - Take first elements        [[1, 30], [2, 15], [3, 10], [5, 6]]
           Ḋ - Dequeue                    [[2, 15], [3, 10], [5, 6]]
caird coinheringaahing
fuente
1

Factor , 58

Bueno, tiene que haber algún factor en esta pregunta.

[ divisors dup reverse zip dup length 1 + 2 /i head rest ]

Es una cita callcon el número en la pila, deja un assoc(un conjunto de pares) en la pila.

Nunca estoy seguro de si todas las importaciones cuentan o no, ya que son parte del lenguaje. Este usa:

USING: math.prime.factors sequences assocs math ;

(Si cuentan, debería buscar una solución más larga con importaciones más cortas, lo cual es un poco tonto)

Como una palabra:

: 2-factors ( x -- a ) divisors dup reverse zip dup length 1 + 2 /i head rest ;

50 2-factors .
 --> { { 2 25 } { 5 10 } }
fede s.
fuente
1

Ruby , 43 bytes

->n{(2..n**0.5).map{|x|[[x,n/x]][n%x]}-[p]}

Pruébalo en línea!

Cómo funciona:

Para cada número hasta sqrt (n), genere el par [[x, n/x]], luego tome el n%xelemento th de esta matriz. Si n%x==0es así [x, n/x], de lo contrario lo es nil. cuando termine, elimine todo nilde la lista.

GB
fuente
1

Pari / GP , 49 34 38 bytes

n->[[d,n/d]|d<-divisors(n),d>1&d<=n/d]

Pruébalo en línea!

Establezca la notación de constructor para todos los pares [d, n/d]donde se dejecuta a través de todos los divisores dde nsujeto a d > 1y d <= n/d.

Gran mejora por alephalpha.

Jeppe Stig Nielsen
fuente
@alephalpha Buena. Pero tuve que cambiarlo un poco porque también generaba la factorización 1.
Jeppe Stig Nielsen
0

Casco , 14 12 bytes

tumoOSe`/⁰Ḋ⁰

Pruébalo en línea!

Explicación

tum(OSe`/⁰)Ḋ⁰  -- input ⁰, eg. 30
           Ḋ⁰  -- divisors [1..⁰]: [1,2,3,5,6,10,15,30]
  m(      )    -- map the following function (example on 10):
     Se        --   create list with 10 and ..
       `/⁰     --   .. flipped division by ⁰ (30/10): [10,3]
    O          --   sort: [3,10]
               -- [[1,30],[2,15],[3,10],[5,6],[5,6],[3,10],[2,15],[1,30]]
 u             -- remove duplicates: [[1,30],[2,15],[3,10],[5,6]]
t              -- tail: [[2,15],[3,10],[5,6]]
ბიმო
fuente
0

APL + WIN, 32 bytes

m,[.1]n÷m←(0=m|n)/m←1↓⍳⌊(n←⎕)*.5

Explicación:

(n←⎕) Prompts for screen input

m←(0=m|n)/m←1↓⍳⌊(n←⎕)*.5 Calculates the factors dropping the first

m,[.1]n÷ Identifies the pairs and concatenates into a list.
Graham
fuente
0

Agregar ++ , 18 15 bytes

L,F@pB]dBRBcE#S

Pruébalo en línea!

Cómo funciona

L,   - Create a lambda function
     - Example argument:     30
  F  - Factors;     STACK = [1 2 3 5 6 10 15]
  @  - Reverse;     STACK = [15 10 6 5 3 2 1]
  p  - Pop;         STACK = [15 10 6 5 3 2]
  B] - Wrap;        STACK = [[15 10 6 5 3 2]]
  d  - Duplicate;   STACK = [[15 10 6 5 3 2] [15 10 6 5 3 2]]
  BR - Reverse;     STACK = [[15 10 6 5 3 2] [2 3 5 6 10 15]]
  Bc - Zip;         STACK = [[15 2] [10 3] [6 5] [5 6] [3 10] [2 15]]
  E# - Sort each;   STACK = [[2 15] [3 10] [5 6] [5 6] [3 10] [2 15]]
  S  - Deduplicate; STACK = [[[2 15] [3 10] [5 6]]]
caird coinheringaahing
fuente
0

Julia 0.6 , 41 bytes

~x=[(y,div(x,y))for y=2:x if x%y<1>y^2-x]

Pruébalo en línea!

Redefine el operador unario incorporado ~y utiliza una comprensión de matriz para generar la salida.

  • div(x,y)es necesario para la división de enteros. x/yahorra 5 bytes pero la salida es~4=(2,2.0) .
  • Julia permite encadenar las comparaciones, ahorrando un byte.
  • Looping todo el camino a x evita Int(floor(√x)).
Lucas
fuente
0

APL NARS 99 caracteres

r←f w;i;h
r←⍬⋄i←1⋄→0×⍳0≠⍴⍴w⋄→0×⍳''≡0↑w⋄→0×⍳w≠⌊w⋄→0×⍳w≠+w
A:i+←1⋄→A×⍳∼0=i∣w⋄→0×⍳i>h←w÷i⋄r←r,⊂i h⋄→A

9 + 46 + 41 + 3 = 99 Prueba: (donde no imprime nada, devuelve algo que devuelve ⍬ la lista nula que hay que considerar como "sin solución")

  f 101    

  f 1 2 3

  f '1'

  f '123'

  f 33 1.23

  f 1.23

  ⎕←⊃f 16777216      
   2 8388608
   4 4194304
   8 2097152
  16 1048576
  32  524288
  64  262144
 128  131072
 256   65536
 512   32768
1024   16384
2048    8192
4096    4096
  f 123
3 41 
RosLuP
fuente
0

Pyt , 67 65 bytes

←ĐðĐ0↔/⅟ƖŽĐŁ₂20`ŕ3ȘĐ05Ș↔ŕ↔Đ4Ș⇹3Ș⦋ƥ⇹⁺Ɩ3ȘĐ05Ș↔ŕ↔Đ4Ș⇹3Ș⦋ƤĐ3Ș⁺ƖĐ3Ș<łĉ

Estoy bastante seguro de que esto se puede jugar al golf.

Básicamente, el algoritmo genera una lista de todos los divisores de la entrada (llamémosla n ), hace la misma lista, pero invertida, intercala los dos (por ejemplo, si n = 24, entonces, en este punto, tiene [ 1,24,2,12,3,8,4,6,6,4,8,3,12,2,24,1]) e imprime los elementos desde el índice 2 hasta la mitad de la longitud de la matriz, imprimiendo cada uno número en una nueva línea, y con una nueva línea adicional entre cada par.

La mayor parte del trabajo se realiza en la gestión real de la pila.


Se guardaron 2 bytes utilizando la función de incremento.

mudkip201
fuente
0

Perl 5, 50 bytes

sub{map[$_,$_[0]/$_],grep!($_[0]%$_),2..sqrt$_[0]}

Sin golf:

sub {
    return map  { [$_, $_[0] / $_] }
           grep { !($_[0] % $_) }
           (2 .. sqrt($_[0]));
}

Pruébalo en línea .

Denis Ibaev
fuente