Znajdź pozytywne dzielniki!

11

Definicja

Liczba jest dodatnia, jeśli jest większa od zera.

Liczba ( A) jest dzielnikiem innej liczby ( B), jeśli Amożna podzielić Bbez reszty.

Na przykład 2jest dzielnikiem, 6ponieważ 2można podzielić 6bez reszty.

Cel

Twoim zadaniem jest napisanie programu / funkcji, która przyjmuje liczbę dodatnią, a następnie znalezienie wszystkich jej dzielników.

Ograniczenie

  • Nie możesz używać żadnych wbudowanych funkcji związanych z liczbą pierwszą lub faktoryzacją .
  • Złożoność algorytmu nie może przekraczać O (sqrt (n)) .

Wolność

  • Lista wyjściowa może zawierać duplikaty.
  • Lista wyników nie musi być sortowana.

Punktacja

To jest . Najkrótsze rozwiązanie w bajtach wygrywa.

Przypadki testowe

input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
Leaky Nun
źródło
Prawdopodobnie masz na myśli dzielnik , a nie czynnik . I myślę, że chcesz mieć złożoność czasową z O(sqrt(n)).
flawr
Jaka jest różnica między dzielnikiem a czynnikiem ?
Leaky Nun
Mówimy o czynnikach np. Liczby, jeśli iloczyn tych wyników ponownie daje liczbę pierwotną, ale dzielnikami są zwykle liczby, które dzielą tę liczbę bez reszty.
flawr
@flawr Odpowiednio zaktualizowany.
Leaky Nun
2
Powinien mieć więcej przykładów. 99 (1 3 9 11 33 99)
Brad Gilbert b2gills

Odpowiedzi:

4

PostgreSQL, 176 bajtów

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

Wejście: (SELECT ...v)

Jak to działa:

  • (SELECT ...v) - Wejście
  • generate_series(1, sqrt(v)::int) - liczby od 1 do sqrt (n)
  • WHERE v%r=0 - dzielniki filtrów
  • zawiń ze wspólnym wyrażeniem tabelowym, aby odwołać się dwukrotnie
  • SELECT r FROM c UNION SELECT v/r FROM c generete reszta dzielników i łącz
  • SELECT string_agg(r::text,',' ORDER BY r) tworzy końcowy wynik oddzielony przecinkami

Wprowadź jako tabelę:

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

Wynik:

╔═════╦════════════════╗
║ 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
źródło
3

C # 6, 75 bajtów

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

Oparty na rozwiązaniu C # downrep_nation, ale rekurencyjny i grał w golfa dalej, wykorzystując kilka nowych funkcji z C # 6.

Podstawowy algorytm jest taki sam jak ten przedstawiony przez downrep_nation. Pętla for zamienia się w rekurencję, a więc drugi parametr. start rekurencji odbywa się za pomocą parametru domyślnego, dlatego funkcja jest wywoływana tylko z wymaganym pojedynczym numerem początkowym.

  • używanie funkcji opartych na wyrażeniach bez bloku pozwala uniknąć instrukcji return
  • interpolacja łańcuchów w operatorze trójskładnikowym pozwala łączyć konkatenację łańcuchów i warunki

Ponieważ większość odpowiedzi tutaj (jeszcze) nie jest zgodna z dokładnym formatem wyjściowym z przykładów, zachowuję go takim, jaki jest, ale wadą jest, że wynik zawiera pojedynczy przecinek końcowy.

jongleur
źródło
Miły pierwszy post!
Rɪᴋᴇʀ
2

Matlab, 48 bajtów

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]
wada
źródło
Jak to działa?
Leaky Nun
Opracowałeś też algorytm, o którym nie mogłem myśleć ... Jak głupi jestem.
Leaky Nun
Znajduję wszystkie podziały do, sqrt(n)a następnie umieszczam każdy dzielnik di n/dna mojej liście.
flawr
Dodano kilka zasad. Może może zaoszczędzić trochę bajtów.
Leaky Nun
1
Nie testowałem, ale czy nie możesz b=~mod(n,a)zapisać 1 bajtu?
Luis Mendo
2

J, 26 bajtów

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

Wyjaśnienie

(],%)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
mile
źródło
2

JavaScript (ES6) - 48 bajtów

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

Niezbyt wydajny, ale działa! Przykład poniżej:

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
źródło
Witamy w PPCG!
Laikoni,
O(n)
1

MATL , 12 bajtów

tX^:\~ftGw/h

Podejście jest podobne do tego w odpowiedzi @ flawr .

Wypróbuj online!

Wyjaśnienie

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
źródło
Często zastanawiam się, czy połączony kod programów napisanych w MATL-ie byłby dobrym RNG.
flawr
@flawr To prawdopodobnie dotyczy prawie każdego języka golfowego :-)
Luis Mendo
1

05AB1E , 14 12 bajtów

Kod:

ÐtLDŠÖÏDŠ/ï«

Wyjaśnienie:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Adnan
źródło
Chcesz podać wyjaśnienie?
Leaky Nun
@KennyLau Dodano
Adnan
1

Python 2, 64 bajty

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

Ta anonimowa funkcja generuje listę dzielników. Dzielniki są obliczane przez próbny podział liczb całkowitych z zakresu [1, ceil(sqrt(n))], który jest O(sqrt(n)). Jeśli n % x == 0(równoważnik n%x<1), a następnie oba xi n/xsą dzielnikami n.

Wypróbuj online

Mego
źródło
1

Galaretka , 9 bajtów

½Rḍ³Tµ³:;

Podobnie jak inne odpowiedzi, jest to O (√n), jeśli przyjmiemy (fałszywe) założenie, że dzielenie liczb całkowitych to O (1) .

Jak to działa

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

Wypróbuj online!

Dennis
źródło
0

Mathematica, 50 bajtów

Podobne do rozwiązania @ flawr .

Wykonuje podział szlaku dla x od 1 do pierwiastka kwadratowego z n, a jeśli jest podzielny, zapisuje go na liście jako x i n / x .

(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  • Zauważ, że wymaga 3 bajtów do reprezentowania w UTF-8, dzięki czemu 48-znakowy ciąg wymaga 50 bajtów w reprezentacji UTF-8.

Stosowanie

  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}
mile
źródło
Cóż, wymaga 3 bajtów ...
Leaky Nun
@KennyLau Tak, myliłem się, powinienem dwukrotnie sprawdzić
mile
0

JavaScript (ES6), 66 62 bajtów

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

Myślałem, że napiszę wersję, która zwróciła posortowaną listę deduplikacji, i okazało się, że jest o 4 bajty krótsza ...

Neil
źródło
0

C #, 87 bajtów


Grał w golfa

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

Nie golfił

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

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

    o += "," + v;

    return o;
}

Pełny kod

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

Wydawnictwa

  • v1.0 - 87 bytes- Wstępne rozwiązanie.

Notatki

  • W kodzie golfowym używam var„i int” zamiast String„i Int32”, aby kod był krótszy, natomiast w kodzie „Ungolfed” i pełnym kodzie używam String„i Int32”, aby kod był bardziej czytelny.
auhmaan
źródło
Słyszałem, że forjest to ogólnie lepsze niż while.
Leaky Nun
Twoje rozwiązanie ma złożoność O (n) zamiast O (sqrt (n)) ...
Leaky Nun
@KennyLau zależy od sytuacji, w tym przypadku forpętla miałaby taką samą długość jak whilepętla. W tym przypadku nie ma znaczenia posiadanie drugiego.
auhmaan
Ale w tym przypadku może ci to uratować bajt ...
Leaky Nun
0

Lua, 83 bajty

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

Niestety nie mogłem nic lepszego

użytkownik6245072
źródło
1. Witamy w PPCG, mam nadzieję, że spodoba ci się ta strona! 2. Możesz zmienić == 0 na <1, aby zapisać niektóre bajty. 3. Możesz użyć trójskładnikowej struktury zamiast jeśli to się skończy, ale nie wiem, czy uratuje jakieś bajty. 4. złożoność algorytmu wynosi O (n), co nie spełnia wymagań.
Leaky Nun
W porządku. Czy lista musi być uporządkowana lub odpowiednio sformatowana?
user6245072
„Lista wyników może zawierać duplikaty. Lista wyników nie musi być sortowana.”
Leaky Nun
Right lol. Czy muszę wydrukować wynik, czy wystarczy tablica z nim zawarta?
user6245072
Cóż, albo go wydrukujesz, albo zwrócisz (wewnątrz funkcji).
Leaky Nun
0

Perl 6 , 40 bajtów

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

Wyjaśnienie:

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

Stosowanie:

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

c #, 87 bajtów

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

nie wiem, czy to działa na wszystkie liczby, podejrzewam, że tak.

ale złożoność jest słuszna, więc to już coś nie jest

downrep_nation
źródło
0

Rubinowy, 56 bajtów

->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}
Wartość tuszu
źródło
0

Kod maszynowy IA-32, 27 bajtów

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

Kod źródłowy (składnia 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;

Pierwszy parametr ( ecx) to wskaźnik do wyjścia, drugi parametr ( edx) to liczba. W żaden sposób nie oznacza końca wyniku; należy wypełnić tablicę wyjściową zerami, aby znaleźć koniec listy.

Pełny program C ++ korzystający z tego kodu:

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

Dane wyjściowe mają pewne usterki, mimo że są zgodne ze specyfikacją (nie ma potrzeby sortowania; nie ma potrzeby wyjątkowości).


Dane wejściowe: 69

Wynik:

69
1
23
3

Dzielniki są w parach.


Wejście: 100

Wynik:

100
1
50
2
25
4
20
5
10
10

Aby uzyskać idealne kwadraty, ostatni dzielnik jest wyprowadzany dwukrotnie (jest to para ze sobą).


Wejście: 30

Wynik:

30
1
15
2
10
3
6
5
5
6

Jeśli dane wejściowe są zbliżone do idealnego kwadratu, ostatnia para jest wysyłana dwukrotnie. Wynika to z kolejności sprawdzania w pętli: najpierw sprawdza „resztę = 0” i wypisuje, a dopiero potem sprawdza „iloraz <dzielnik”, aby wyjść z pętli.

anatolig
źródło
0

SmileBASIC, 49 bajtów

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

Wykorzystuje fakt, że D>N/D= D>sqrt(N)dla liczb dodatnich

12Me21
źródło
0

C, 87 81 bajtów

Poprawiony przez @ceilingcat , 81 bajtów:

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

Wypróbuj online!


Moja oryginalna odpowiedź, 87 bajtów:

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

Kompiluj gcc div.c -o div -lmi uruchamiaj z ./div <n>.


Bonus: jeszcze krótszy wariant ze złożonością czasową O (n) i zakodowany na stałe n(46 bajtów + długość n):

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

Edycja: Dziękuję @Sriotchilism O'Zaic za wskazanie, że dane wejściowe nie powinny być zakodowane na stałe, zmodyfikowałem główne przesłanie, aby pobrać dane za pośrednictwem argv.

OverclockedSanic
źródło
1
Czy ndane wejściowe? Umieszczanie danych wejściowych w zmiennej nie jest tutaj przyjętym sposobem z wielu powodów. Możesz dowiedzieć się więcej o naszych przyjętych i non-Przyjmujemy tu wejściowych i wyjściowych: codegolf.meta.stackexchange.com/questions/2447/... . A jeśli interesuje Cię konkretny język (np. C), możesz zajrzeć tutaj: codegolf.meta.stackexchange.com/questions/11924/… .
Ad Hoc Garf Hunter
@ SriotchilismO'Zaic Tak, nto dane wejściowe. Spróbuję go zmodyfikować, aby pobierał dane wejściowe w inny sposób. Dziękuję za informację!
OverclockedSanic
0

APL (NARS), 22 znaki, 44 bajty

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

test:

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