Finde die positiven Teiler!

11

Definition

Eine Zahl ist positiv, wenn sie größer als Null ist.

Eine Zahl ( A) ist der Teiler einer anderen Zahl ( B), wenn Asie Bohne Rest geteilt werden kann.

Zum Beispiel 2ist ein Teiler von 6weil 2kann 6ohne Rest teilen .

Tor

Ihre Aufgabe ist es, ein Programm / eine Funktion zu schreiben, die eine positive Zahl annimmt, und dann alle ihre Teiler zu finden.

Beschränkung

  • Sie dürfen keine eingebauten Elemente in Bezug auf Primzahl oder Faktorisierung verwenden .
  • Die Komplexität Ihres Algorithmus darf O (sqrt (n)) nicht überschreiten .

Freiheit

  • Die Ausgabeliste kann Duplikate enthalten.
  • Die Ausgabeliste muss nicht sortiert werden.

Wertung

Das ist . Die kürzeste Lösung in Bytes gewinnt.

Testfälle

input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
Undichte Nonne
quelle
Sie meinen wahrscheinlich Teiler , nicht Faktor . Und ich denke, Sie möchten eine zeitliche Komplexität von haben O(sqrt(n)).
Fehler
Was ist der Unterschied zwischen Divisor und Faktor ?
Undichte Nonne
Wir sprechen über Faktoren von z. B. einer Zahl, wenn das Produkt aus diesen wieder die ursprüngliche Zahl ergibt, aber die Teiler sind normalerweise die Zahlen, die diese Zahl ohne Rest teilen .
Fehler
@flawr Entsprechend aktualisiert.
Undichte Nonne
2
Sollte mehr Beispiele haben. 99 (1 3 9 11 33 99)
Brad Gilbert b2gills

Antworten:

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

Eingang: (SELECT ...v)

Wie es funktioniert:

  • (SELECT ...v) - Eingabe
  • generate_series(1, sqrt(v)::int) - Zahlen von 1 bis sqrt (n)
  • WHERE v%r=0 -Filterteiler
  • Wrap mit allgemeinem Tabellenausdruck, um zweimal zu verweisen
  • SELECT r FROM c UNION SELECT v/r FROM c Rest der Teiler erzeugen und kombinieren
  • SELECT string_agg(r::text,',' ORDER BY r) das durch Kommas getrennte Endergebnis erzeugen

Eingabe als Tabelle:

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

Ausgabe:

╔═════╦════════════════╗
║ 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
quelle
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);

Basierend auf der C # -Lösung von downrep_nation, jedoch rekursiv und weiter unten mit einigen neuen Funktionen von C # 6 gespielt.

Der grundlegende Algorithmus ist der gleiche wie der von downrep_nation. Die for-Schleife wird in eine Rekursion umgewandelt, also der zweite Parameter. Der Rekursionsstart erfolgt über den Standardparameter, daher wird die Funktion nur mit der erforderlichen einzelnen Startnummer aufgerufen.

  • Durch die Verwendung ausdrucksbasierter Funktionen ohne Block wird die return-Anweisung vermieden
  • Die String-Interpolation innerhalb des ternären Operators ermöglicht die Verknüpfung von String-Verkettung und -Bedingungen

Da die meisten Antworten hier (noch) nicht dem genauen Ausgabeformat aus den Beispielen folgen, behalte ich es so wie es ist, aber als Nachteil enthält die Funktion ein einzelnes nachfolgendes Komma im Ergebnis.

Jongleur
quelle
Schöner erster Beitrag!
Rɪᴋᴇʀ
2

Matlab, 48 Bytes

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]
fehlerhaft
quelle
Wie funktioniert das?
Undichte Nonne
Außerdem haben Sie einen Algorithmus entwickelt, an den ich nicht denken konnte ... Wie dumm ich bin.
Undichte Nonne
Ich finde alle Divisos bis zu sqrt(n)und füge dann jeden Divisor dund n/din meine Liste ein.
Fehler
Einige Regeln hinzugefügt. Vielleicht könnten Sie einige Bytes sparen.
Undichte Nonne
1
Ich habe nicht getestet, aber können Sie nicht b=~mod(n,a)1 Byte speichern?
Luis Mendo
2

J, 26 Bytes

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

Erläuterung

(],%)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
Meilen
quelle
2

JavaScript (ES6) - 48 Bytes

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

Nicht sehr effizient, funktioniert aber! Beispiel unten:

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
quelle
Willkommen bei PPCG!
Laikoni
O(n)
1

MATL , 12 Bytes

tX^:\~ftGw/h

Der Ansatz ähnelt dem in der Antwort von @ errorr .

Probieren Sie es online aus!

Erläuterung

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
quelle
Ich frage mich oft, ob der kombinierte Code von Programmen, die in MATL geschrieben wurden, ein gutes RNG ergeben würde.
Fehler
@flawr Das gilt wahrscheinlich für so ziemlich jede Code-Golfsprache :-)
Luis Mendo
1

05AB1E , 14 12 Bytes

Code:

ÐtLDŠÖÏDŠ/ï«

Erläuterung:

Ð             # 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.

Verwendet die CP-1252- Codierung. Probieren Sie es online aus! .

Adnan
quelle
Möchten Sie eine Erklärung geben?
Undichte Nonne
@ KennyLau Hinzugefügt
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],[])

Diese anonyme Funktion gibt eine Liste von Teilern aus. Die Teiler werden durch Versuchsteilung von ganzen Zahlen in dem Bereich berechnet [1, ceil(sqrt(n))], der ist O(sqrt(n)). Wenn n % x == 0(äquivalent zu n%x<1), dann sind beide xund n/xTeiler von n.

Probieren Sie es online aus

Mego
quelle
1

Gelee , 9 Bytes

½Rḍ³Tµ³:;

Wie die anderen Antworten, ist dies O (√n), wenn wir die (falsche) Annahme machen, dass die ganzzahlige Division O (1) ist .

Wie es funktioniert

½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.

Probieren Sie es online aus!

Dennis
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Dennis
1

Javascript, 47 Bytes

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

Paulo
quelle
0

Mathematica, 50 Bytes

Ähnlich @ flawr der Lösung .

Führt eine Spurteilung für x von 1 bis zur Quadratwurzel von n durch und speichert sie, falls teilbar, in einer Liste als x und n / x .

(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  • Beachten Sie, dass für die Darstellung in UTF-8 3 Byte erforderlich sind, sodass für die 48-Zeichen-Zeichenfolge in der UTF-8-Darstellung 50 Byte erforderlich sind.

Verwendung

  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}
Meilen
quelle
Nun, es erfordert 3 Bytes ...
Leaky Nun
@KennyLau Ja, ich habe mich geirrt, hätte es noch einmal überprüfen sollen
Meilen
0

JavaScript (ES6), 66 62 Byte

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

Ich dachte, ich würde eine Version schreiben, die eine sortierte deduplizierte Liste zurückgibt, und es stellte sich heraus, dass sie 4 Bytes kürzer war ...

Neil
quelle
0

C #, 87 Bytes


Golf gespielt

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

Ungolfed

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

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

    o += "," + v;

    return o;
}

Vollständiger Code

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

Veröffentlichungen

  • v1.0 - 87 bytes- Erste Lösung.

Anmerkungen

  • Im Golfed-Code verwende ich var's und int' s anstelle von String's und Int32' s, um den Code zu verkürzen , während ich im Ungolfed-Code und im vollständigen CodeString 's und Int32' s verwende, um den Code lesbarer zu machen.
Auhmaan
quelle
Ich habe gehört, das forist im Allgemeinen besser als while.
Undichte Nonne
Ihre Lösung hat eine Komplexität von O (n) anstelle von O (sqrt (n)) ...
Leaky Nun
@KennyLau es hängt von der Situation ab, in diesem Fall hätte eine forSchleife die gleiche Länge wie die whileSchleife. In diesem Fall ist es irrelevant, ein oder das andere zu haben.
Auhmaan
Aber in diesem Fall kann es Ihnen ein Byte sparen ...
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))

Ich könnte es leider nicht besser machen

user6245072
quelle
1. Willkommen bei PPCG, ich hoffe, Sie werden diese Seite genießen! 2. Sie können == 0 in <1 ändern, um einige Bytes zu sparen. 3. Sie können die ternäre Struktur anstelle von if then end verwenden, aber ich weiß nicht, ob dadurch Bytes gespeichert werden. 4. Die Komplexität Ihres Algorithmus ist O (n), was die Anforderung nicht erfüllt.
Undichte Nonne
Gut. Muss die Liste bestellt oder entsprechend formatiert werden?
user6245072
"Die Ausgabeliste kann Duplikate enthalten. Die Ausgabeliste muss nicht sortiert werden."
Leaky Nun
Richtig lol. Und muss ich das Ergebnis drucken oder reicht ein Array aus, das es enthält?
user6245072
Nun, entweder drucken Sie es aus oder Sie geben es zurück (innerhalb einer Funktion).
Undichte Nonne
0

Perl 6 , 40 Bytes

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

Erläuterung:

{
  # 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
  )
}

Verwendung:

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

Ich weiß nicht, ob dies für alle Zahlen funktioniert, ich vermute, dass es funktioniert.

aber die Komplexität stimmt, also ist das schon etwas, nicht wahr?

downrep_nation
quelle
0

Ruby, 56 Bytes

->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}
Wert Tinte
quelle
0

IA-32 Maschinencode, 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

Quellcode (MS Visual Studio-Syntax):

    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;

Der erste Parameter ( ecx) ist ein Zeiger auf die Ausgabe, der zweite Parameter ( edx) ist die Zahl. Es markiert in keiner Weise das Ende der Ausgabe. Man sollte das Ausgabearray mit Nullen füllen, um das Ende der Liste zu finden.

Ein vollständiges C ++ - Programm, das diesen Code verwendet:

#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';
}

Die Ausgabe weist einige Störungen auf, obwohl sie der Spezifikation folgt (keine Notwendigkeit zum Sortieren; keine Notwendigkeit zur Eindeutigkeit).


Eingabe: 69

Ausgabe:

69
1
23
3

Die Teiler sind paarweise.


Eingabe: 100

Ausgabe:

100
1
50
2
25
4
20
5
10
10

Für perfekte Quadrate wird der letzte Divisor zweimal ausgegeben (es ist ein Paar mit sich selbst).


Eingabe: 30

Ausgabe:

30
1
15
2
10
3
6
5
5
6

Wenn sich die Eingabe einem perfekten Quadrat nähert, wird das letzte Paar zweimal ausgegeben. Dies liegt an der Reihenfolge der Überprüfungen in der Schleife: Zuerst wird nach "Rest = 0" und Ausgaben gesucht, und erst dann wird nach "Quotient <Divisor" gesucht, um die Schleife zu verlassen.

Anatolyg
quelle
0

SmileBASIC, 49 Bytes

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

Verwendet die Tatsache, dass D>N/D= D>sqrt(N)für positive Zahlen

12Me21
quelle
0

C 87 81 Bytes

Verbessert durch @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));}

Probieren Sie es online aus!


Meine ursprüngliche Antwort, 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));}

Kompilieren mit gcc div.c -o div -lmund ausführen mit ./div <n>.


Bonus: Eine noch kürzere Variante mit O (n) Zeitkomplexität und fest codiert n(46 Bytes + Länge von n):

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

Bearbeiten: Vielen Dank an @Sriotchilism O'Zaic für den Hinweis, dass Eingaben nicht fest codiert werden sollten. Ich habe die Hauptübermittlung geändert, um die Eingabe über argv zu übernehmen.

OverclockedSanic
quelle
1
Ist ndie Eingabe? Das Einfügen der Eingabe in eine Variable ist aus mehreren Gründen keine akzeptierte Methode zum Eingeben. Weitere Informationen zu unseren akzeptierten und nicht akzeptierten Eingabe- und Ausgabeformularen finden Sie hier: codegolf.meta.stackexchange.com/questions/2447/… . Und wenn Sie neugierig auf eine bestimmte Sprache sind (z. B. C), können Sie hier nachsehen : codegolf.meta.stackexchange.com/questions/11924/… .
Post Rock Garf Hunter
@ SriotchilismO'Zaic Ja, nist die Eingabe. Ich werde versuchen, es so zu ändern, dass die Eingabe auf eine andere Weise erfolgt. Danke für die Info!
OverclockedSanic
0

APL (NARS), 22 Zeichen, 44 Bytes

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

Prüfung:

  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
quelle