Encuentra los divisores positivos!

11

Definición

Un número es positivo si es mayor que cero.

Un número ( A) es el divisor de otro número ( B) si Apuede dividirse Bsin resto.

Por ejemplo, 2es un divisor de 6porque 2puede dividirse 6sin resto.

Objetivo

Su tarea es escribir un programa / función que tome un número positivo y luego encontrar todos sus divisores.

Restricción

  • No puede utilizar ninguna función integrada relacionada con la prima o la factorización .
  • La complejidad de su algoritmo no debe exceder O (sqrt (n)) .

Libertad

  • La lista de salida puede contener duplicados.
  • La lista de salida no necesita ser ordenada.

Puntuación

Este es el . La solución más corta en bytes gana.

Casos de prueba

input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
Monja permeable
fuente
Probablemente quieras decir divisor , no factor . Y supongo que quieres tener una complejidad de tiempoO(sqrt(n)) .
flawr
¿Cuál es la diferencia entre divisor y factor ?
Leaky Nun
Hablamos de factores como, por ejemplo, un número, si el producto de estos resulta en el número original nuevamente, pero los divisores son generalmente los números que dividen dicho número sin dejar resto.
flawr
@flawr Actualizado en consecuencia.
Leaky Nun
2
Debería tener más ejemplos. 99 (1 3 9 11 33 99)
Brad Gilbert b2gills

Respuestas:

4

PostgreSQL, 176 bytes

WITH c AS(SELECT * FROM(SELECT 6v)t,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT string_agg(r::text,',' ORDER BY r)
FROM(SELECT r FROM c UNION SELECT v/r FROM c)s

SqlFiddleDemo

Entrada: (SELECT ...v)

Cómo funciona:

  • (SELECT ...v) - entrada
  • generate_series(1, sqrt(v)::int) - números del 1 al sqrt (n)
  • WHERE v%r=0 divisores de filtro
  • envolver con expresión de tabla común para referir dos veces
  • SELECT r FROM c UNION SELECT v/r FROM c generete resto de divisores y combinan
  • SELECT string_agg(r::text,',' ORDER BY r) producir un resultado final separado por comas

Entrada como tabla:

WITH c AS(SELECT * FROM i,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT v,string_agg(r::text,',' ORDER BY r)
FROM(SELECT v,r FROM c UNION SELECT v,v/r FROM c)s
GROUP BY v

SqlFiddleDemo

Salida:

╔═════╦════════════════╗
║ v   ║   string_agg   ║
╠═════╬════════════════╣
║  1  ║ 1              ║
║  2  ║ 1,2            ║
║  6  ║ 1,2,3,6        ║
║  9  ║ 1,3,9          ║
║ 99  ║ 1,3,9,11,33,99 ║
╚═════╩════════════════╝
lad2025
fuente
3

C # 6, 75 bytes

string f(int r,int i=1)=>i*i>r?"":r%i==0?$"{i},{n(r,i+1)}{r/i},":n(r,i+1);

Basado en la solución C # de downrep_nation, pero recursivo y más avanzado utilizando algunas características nuevas de C # 6.

El algoritmo básico es el mismo que el presentado por downrep_nation. El bucle for se convierte en una recursividad, por lo tanto, el segundo parámetro. el inicio predeterminado se realiza mediante el parámetro predeterminado, por lo tanto, la función se llama solo con el número de inicio requerido.

  • el uso de funciones basadas en expresiones sin un bloque evita la declaración de retorno
  • La interpolación de cadenas dentro del operador ternario permite unir condiciones y concatenación de cadenas

Como la mayoría de las respuestas aquí (todavía) no siguen el formato de salida exacto de los ejemplos, lo mantengo como está, pero como inconveniente, la función incluye una coma final en el resultado.

jongleur
fuente
Bonito primer post!
Rɪᴋᴇʀ
3

R , 36 31 bytes

n=scan();c(d<-1:n^.5,n/d)^!n%%d

Pruébalo en línea!

-5 bytes gracias a Robin Ryder

Giuseppe
fuente
32 bytes con en n^.5lugar de sqrt(n).
Robin Ryder
Puede bajar a 31 bytes duplicando las 1muchas veces.
Robin Ryder
@RobinRyder inteligente! Gracias.
Giuseppe
2

Matlab, 48 bytes

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]
falla
fuente
¿Como funciona esto?
Leaky Nun
Además, ideaste un algoritmo en el que no podía pensar ... Qué estúpido soy.
Leaky Nun
Encuentro todos los divisos sqrt(n)y luego pongo cada divisor dy n/den mi lista.
defecto
Se agregaron algunas reglas. Tal vez podría ahorrarte algunos bytes.
Leaky Nun
1
No lo he probado, pero ¿no puedes usar b=~mod(n,a)para guardar 1 byte?
Luis Mendo
2

J 26 bytes

(],%)1+[:I.0=]|~1+i.@<.@%:

Explicación

(],%)1+[:I.0=]|~1+i.@<.@%:  Input: n
                        %:  Sqrt(n)
                     <.@    Floor(Sqrt(n))
                  i.@       Get the range from 0 to Floor(Sqrt(n)), exclusive
                1+          Add 1 to each
             ]              Get n
              |~            Get the modulo of each in the range by n
           0=               Which values are equal to 0 (divisible by n), 1 if true else 0
       [:I.                 Get the indices of ones
     1+                     Add one to each to get the divisors of n less than sqrt(n)
   %                        Divide n by each divisor
 ]                          Get the divisors
  ,                         Concatenate them and return
millas
fuente
2

JavaScript (ES6) - 48 bytes

f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x))

¡No muy eficiente pero funciona! Ejemplo a continuación:

let f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x));
document.querySelector("input").addEventListener("change", function() {
  document.querySelector("output").value = f(Number(this.value)).join(", ");
});
Divisors of <input type="number" min=0 step=1> are: <output></output>

Kamila Skonieczna
fuente
Bienvenido a PPCG!
Laikoni
Esto es y, como tal, no es válido. O(n)
ბიმო
1

MATL , 12 bytes

tX^:\~ftGw/h

El enfoque es similar al de la respuesta de @ flawr .

Pruébalo en línea!

Explicación

t      % take input N. Duplicate.
X^:    % Generate range from 1 to sqrt(N)
\      % modulo (remainder of division)
~f     % indices of zero values: array of divisors up to sqrt(N)
tGw/   % element-wise divide input by those divisors, to produce rest of divisors
h      % concatenate both arrays horizontally
Luis Mendo
fuente
A menudo me pregunto si el código combinado de los programas escritos en MATL sería un buen RNG.
falla
@flawr Eso probablemente se aplica a casi todos los lenguajes de golf de código :-)
Luis Mendo
1

05AB1E , 14 12 bytes

Código:

ÐtLDŠÖÏDŠ/ï«

Explicación:

Ð             # Triplicate input.
 tL           # Push the list [1, ..., sqrt(input)].
   D          # Duplicate that list.
    Š         # Pop a,b,c and push c,a,b.
     Ö        # Check for each if a % b == 0.
      Ï       # Only keep the truthy elements.
       D      # Duplicate the list.
        Š     # Pop a,b,c and push c,a,b
         /ï   # Integer divide
           «  # Concatenate to the initial array and implicitly print.

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
¿Te importaría dar una explicación?
Leaky Nun
@KennyLau Añadido
Adnan
1

Python 2, 64 bytes

lambda n:sum([[x,n/x]for x in range(1,int(n**.5+1))if n%x<1],[])

Esta función anónima genera una lista de divisores. Los divisores se calculan por la división de prueba de los enteros en el rango [1, ceil(sqrt(n))], que es O(sqrt(n)). Si n % x == 0(equivalente a n%x<1), entonces ambos xy n/xson divisores de n.

Pruébalo en línea

Mego
fuente
1

Jalea , 9 bytes

½Rḍ³Tµ³:;

Como las otras respuestas, esto es O (√n) si hacemos la suposición (falsa) de que la división entera es O (1) .

Cómo funciona

½Rḍ³Tµ³:;  Main link. Argument: n

½          Compute the square root of n.
 R         Construct the range from 1 to the square root.
  ḍ³       Test each integer of that range for divisibility by n.
    T      Get the indices of truthy elements.
     µ     Begin a new, monadic chain. Argument: A (list of divisors)
      ³:   Divide n by each divisor.
        ;  Concatenate the quotients with A.

Pruébalo en línea!

Dennis
fuente
Continuemos esta discusión en el chat .
Dennis
1

Javascript, 47 bytes

d=(n,f=1,s='')=>n==f?s+n:d(n,f+1,n%f?s:s+f+',')

Paulo
fuente
0

Mathematica, 50 bytes

Similar a la solución de @ flawr .

Realiza la división del rastro para x desde 1 hasta la raíz cuadrada de n y, si es divisible, la guarda en una lista como x y n / x .

(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  • Tenga en cuenta que requiere 3 bytes para representar en UTF-8, por lo que la cadena de 48 caracteres requiere 50 bytes en representación UTF-8.

Uso

  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  f[1]
{1, 1}
  f[2]
{2, 1}
  f[6]
{6, 3, 1, 2}
  f[9]
{9, 3, 1, 3}
millas
fuente
Bueno, requiere 3 bytes ...
Leaky Nun
@KennyLau Sí, me equivoqué, debería haber verificado dos veces
millas
0

JavaScript (ES6), 66 62 bytes

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

Pensé en escribir una versión que devolviera una lista desduplicada ordenada, y en realidad resultó ser 4 bytes más corta ...

Neil
fuente
0

C #, 87 bytes


Golfed

String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}

Sin golf

String m( Int32 v ) {
    String o = "1";
    Int32 i = 1;

    while (++i <= v / 2)
        if (v % i == 0)
            o += "," + i;

    o += "," + v;

    return o;
}

Código completo

using System;
using System.Collections.Generic;

namespace N {
    class P {
        static void Main( string[] args ) {
            List<Int32> li = new List<Int32>() {
                1, 2, 6, 9,
            };

            foreach (Int32 i in li) {
                Console.WriteLine( i + " »> " + m( i ) );
            }

            Console.ReadLine();
        }

        static String m( Int32 v ) {
            String o = "1";
            Int32 i = 1;

            while (++i <= v / 2)
                if (v % i == 0)
                    o += "," + i;

            o += "," + v;

            return o;
        }
    }
}

Lanzamientos

  • v1.0 - 87 bytes- Solución inicial.

Notas

  • En el código Golfed , uso var'sy int' s en lugar de String'sy Int32' s para acortar el código, mientras que en el código Ungolfed y Full Code uso String'sy Int32' s para que el código sea más legible.
auhmaan
fuente
He escuchado que forgeneralmente es mejor que while.
Leaky Nun
Su solución tiene una complejidad de O (n) en lugar de O (sqrt (n)) ...
Leaky Nun
@KennyLau depende de la situación, en este caso tener un forbucle tendría la misma longitud que el whilebucle. En este caso es irrelevante tener o tener el otro.
auhmaan
Pero en este caso puede ahorrarte un byte ...
Leaky Nun
0

Lua, 83 bytes

s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))

No podría hacerlo mejor, desafortunadamente

usuario6245072
fuente
1. Bienvenido a PPCG, ¡espero que disfrutes de este sitio! 2. puede cambiar == 0 a <1 para guardar algunos bytes. 3. puede usar la estructura ternaria en lugar de if y end, pero no sé si guardará algún byte. 4. La complejidad de su algoritmo es O (n) que no cumple con el requisito.
Leaky Nun
Todo bien. ¿La lista necesita ser ordenada o formateada adecuadamente?
user6245072
"La lista de salida puede contener duplicados. La lista de salida no necesita ser ordenada".
Leaky Nun
Correcto jajaja. ¿Y necesito imprimir el resultado o una matriz que lo contiene es suficiente?
user6245072
Bueno, o lo imprimes o lo devuelves (dentro de una función).
Leaky Nun
0

Perl 6 , 40 bytes

{|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

Explicación:

{
  # this block has an implicit parameter named $_

  # slip this list into outer list:
  |(

    my @a = grep
                 # Whatever lambda:
                 # checks if the block's parameter ($_)
                 # is divisible by (%%) this lambda's parameter (*)

                 $_ %% *,

                 # upto and exclude the sqrt of the argument
                 # then shift the Range up by one
                 ^.sqrt+1
                 # (0 ..^ $_.sqrt) + 1

                 # would be clearer if written as:
                 # 1 .. $_.sqrt+1
  ),
  # slip this list into outer list
  |(

    # take the argument and divide it by each value in @a
    $_ X/ @a

    # should use X[div] instead of X[/] so that it would return
    # Ints instead of Rats
  )
}

Uso:

my &divisors = {|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

.say for (1,2,6,9,10,50,99)».&divisors
(1 1)
(1 2 2 1)
(1 2 3 6 3 2)
(1 3 9 3)
(1 2 10 5)
(1 2 5 50 25 10)
(1 3 9 99 33 11)
Brad Gilbert b2gills
fuente
0

c #, 87 bytes

void f(int r){for(int i=1;i<=Math.Sqrt(r);i++){if(r%i==0)Console.WriteLine(i+" "+r/i);}

No sé si esto funciona para todos los números, sospecho que sí.

pero la complejidad es correcta, entonces eso ya no es algo

downrep_nation
fuente
0

Ruby, 56 bytes

->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}
Tinta de valor
fuente
0

Código de máquina IA-32, 27 bytes

Hexdump:

60 33 db 8b f9 33 c0 92 43 50 f7 f3 85 d2 75 04
ab 93 ab 93 3b c3 5a 77 ec 61 c3

Código fuente (sintaxis de MS Visual Studio):

    pushad;
    xor ebx, ebx;
    mov edi, ecx;
myloop:
    xor eax, eax;
    xchg eax, edx;
    inc ebx;
    push eax;
    div ebx;
    test edx, edx;
    jnz skip_output;
    stosd;
    xchg eax, ebx;
    stosd;
    xchg eax, ebx;
skip_output:
    cmp eax, ebx;
    pop edx;
    ja myloop;
    popad;
    ret;

El primer parámetro ( ecx) es un puntero a la salida, el segundo parámetro ( edx) es el número. No marca el final de la salida de ninguna manera; uno debe completar previamente la matriz de salida con ceros para encontrar el final de la lista.

Un programa completo de C ++ que usa este código:

#include <cstdint>
#include <vector>
#include <iostream>
#include <sstream>
__declspec(naked) void _fastcall doit(uint32_t* d, uint32_t n) {
    _asm {
        pushad;
        xor ebx, ebx;
        mov edi, ecx;
    myloop:
        xor eax, eax;
        xchg eax, edx;
        inc ebx;
        push eax;
        div ebx;
        test edx, edx;
        jnz skip_output;
        stosd;
        xchg eax, ebx;
        stosd;
        xchg eax, ebx;
    skip_output:
        cmp eax, ebx;
        pop edx;
        ja myloop;
        popad;
        ret;
    }
}
int main(int argc, char* argv[]) {
    uint32_t n;
    std::stringstream(argv[1]) >> n;
    std::vector<uint32_t> list(2 * sqrt(n) + 3); // c++ initializes with zeros
    doit(list.data(), n);
    for (auto i = list.begin(); *i; ++i)
        std::cout << *i << '\n';
}

La salida tiene algunos problemas técnicos, a pesar de que sigue las especificaciones (no es necesario ordenarlos, no es necesario que sean únicos).


Entrada: 69

Salida:

69
1
23
3

Los divisores están en pares.


Entrada: 100

Salida:

100
1
50
2
25
4
20
5
10
10

Para cuadrados perfectos, el último divisor se emite dos veces (es un par consigo mismo).


Entrada: 30

Salida:

30
1
15
2
10
3
6
5
5
6

Si la entrada está cerca de un cuadrado perfecto, el último par sale dos veces. Se debe al orden de las verificaciones en el bucle: primero, verifica "resto = 0" y las salidas, y solo luego verifica "cociente <divisor" para salir del bucle.

anatolyg
fuente
0

SmileBASIC, 49 bytes

INPUT N
FOR D=1TO N/D
IF N MOD D<1THEN?D,N/D
NEXT

Utiliza el hecho de que D>N/D= D>sqrt(N)para números positivos

12Me21
fuente
0

C, 87 81 bytes

Mejorado por @ceilingcat , 81 bytes:

i,j;main(n,b)int**b;{for(;j=sqrt(n=atoi(b[1]))/++i;n%i||printf("%u,%u,",i,n/i));}

Pruébalo en línea!


Mi respuesta original, 87 bytes:

i;main(int n,char**b){n=atoi(b[1]);for(;(int)sqrt(n)/++i;n%i?:printf("%u,%u,",i,n/i));}

Compilar gcc div.c -o div -lmy ejecutar con ./div <n>.


Bonificación: una variante aún más corta con complejidad de tiempo O (n) y codificada n(46 bytes + longitud de n):

i,n=/*INSERT VALUE HERE*/;main(){for(;n/++i;n%i?:printf("%u,",i));}

Editar: Gracias a @Sriotchilism O'Zaic por señalar que las entradas no deben codificarse, modifiqué la presentación principal para tomar la entrada a través de argv.

OverclockedSanic
fuente
1
Es nla entrada? Poner la entrada en una variable no es una forma aceptada de hacer entrada aquí por varias razones. Puede ver más sobre nuestros formularios de entrada y salida aceptados y no aceptados aquí: codegolf.meta.stackexchange.com/questions/2447/… . Y si tiene curiosidad acerca de un lenguaje específico (por ejemplo, C) puede buscar aquí: codegolf.meta.stackexchange.com/questions/11924/… .
Ad Hoc Garf Hunter
@ SriotchilismO'Zaic Sí, nes la entrada. Intentaré modificarlo para que tome la entrada de otra manera. ¡Gracias por la información!
OverclockedSanic
0

APL (NARS), 22 caracteres, 44 bytes

{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}

prueba:

  f←{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}
  f 1
1 
  f 2
1 2 
  f 6
1 2 6 3 
  f 9
1 3 9 
  f 90
1 2 3 5 6 9 90 45 30 18 15 10 
RosLuP
fuente