Temukan pembagi positif!

11

Definisi

Angka positif jika lebih besar dari nol.

Angka ( A) adalah pembagi nomor lain ( B) jika Adapat dibagi Btanpa sisa.

Misalnya, 2adalah pembagi 6karena 2bisa membelah 6tanpa sisa.

Tujuan

Tugas Anda adalah menulis program / fungsi yang mengambil angka positif dan kemudian menemukan semua pembagi nya.

Larangan

  • Anda tidak boleh menggunakan bawaan apa pun yang terkait dengan prima atau faktorisasi .
  • Kompleksitas algoritma Anda tidak boleh melebihi O (sqrt (n)) .

Kebebasan

  • Daftar output dapat berisi duplikat.
  • Daftar output tidak perlu disortir.

Mencetak gol

Ini adalah . Solusi terpendek dalam byte menang.

Testcases

input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
Biarawati Bocor
sumber
Anda mungkin berarti pembagi , bukan faktor . Dan saya kira Anda ingin memiliki kompleksitas waktu dari O(sqrt(n)).
flawr
Apa perbedaan antara pembagi dan faktor ?
Leaky Nun
Kita berbicara tentang faktor-faktor misalnya angka, jika produk dari hasil ini dalam angka asli lagi, tetapi pembagi biasanya angka-angka yang membagi angka tersebut tanpa sisa.
flawr
@ flawr Diperbarui sesuai.
Leaky Nun
2
Seharusnya punya lebih banyak contoh. 99 (1 3 9 11 33 99)
Brad Gilbert b2gills

Jawaban:

4

PostgreSQL, 176 byte

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

Memasukkan: (SELECT ...v)

Bagaimana itu bekerja:

  • (SELECT ...v) - memasukkan
  • generate_series(1, sqrt(v)::int) - angka dari 1 hingga sqrt (n)
  • WHERE v%r=0 pembagi-filter
  • bungkus dengan ekspresi tabel umum untuk merujuk dua kali
  • SELECT r FROM c UNION SELECT v/r FROM c sisa pembagi dan menggabungkan
  • SELECT string_agg(r::text,',' ORDER BY r) menghasilkan hasil akhir yang dipisahkan koma

Masukan sebagai 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

Keluaran:

╔═════╦════════════════╗
║ 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
sumber
3

C # 6, 75 byte

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

Berdasarkan solusi C # dari downrep_nation, tetapi rekursif dan golf lebih lanjut menggunakan beberapa fitur baru dari C # 6.

Algoritma dasar sama dengan yang disajikan oleh downrep_nation. For-loop diubah menjadi rekursi, dengan demikian parameter kedua. awal rekursi dilakukan oleh parameter default, sehingga fungsinya dipanggil dengan nomor awal tunggal yang diperlukan saja.

  • menggunakan fungsi berbasis ekspresi tanpa blok menghindari pernyataan kembali
  • interpolasi string dalam operator ternary memungkinkan untuk bergabung dengan rangkaian dan kondisi string

Karena sebagian besar jawaban di sini (belum) tidak mengikuti format output yang tepat dari contoh, saya menyimpannya apa adanya, tetapi sebagai kekurangannya fungsi ini menyertakan koma jejak tunggal pada hasilnya.

jongleur
sumber
Posting pertama yang bagus!
Rɪᴋᴇʀ
3

R , 36 31 byte

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

Cobalah online!

-5 byte terima kasih kepada Robin Ryder

Giuseppe
sumber
32 byte dengan n^.5bukannya sqrt(n).
Robin Ryder
Anda dapat turun ke 31 byte dengan menduplikasi 1berkali-kali.
Robin Ryder
@RobinRyder pintar! Terima kasih.
Giuseppe
2

Matlab, 48 byte

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]
cacat
sumber
Bagaimana cara kerjanya?
Leaky Nun
Juga, Anda membuat algoritma yang tidak bisa saya pikirkan ... Betapa bodohnya saya.
Leaky Nun
Saya menemukan semua divisi hingga sqrt(n)dan kemudian menempatkan masing-masing pembagi ddan n/ddalam daftar saya.
flawr
Menambahkan beberapa aturan. Mungkin bisa menghemat beberapa byte.
Leaky Nun
1
Saya belum diuji, tetapi tidak bisakah Anda menggunakan b=~mod(n,a)untuk menyimpan 1 byte?
Luis Mendo
2

J, 26 byte

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

Penjelasan

(],%)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
mil
sumber
2

JavaScript (ES6) - 48 byte

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

Tidak terlalu efisien tetapi berfungsi! Contoh di bawah ini:

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
sumber
Selamat datang di PPCG!
Laikoni
HAI(n)
1

MATL , 12 byte

tX^:\~ftGw/h

Pendekatannya mirip dengan yang ada di jawaban @ flawr .

Cobalah online!

Penjelasan

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
sumber
Saya sering bertanya-tanya apakah kode program gabungan yang ditulis dalam MATL akan menjadi RNG yang baik.
flawr
@ flawr Itu mungkin berlaku untuk hampir setiap bahasa kode golf :-)
Luis Mendo
1

05AB1E , 14 12 byte

Kode:

ÐtLDŠÖÏDŠ/ï«

Penjelasan:

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

Menggunakan pengodean CP-1252 . Cobalah online! .

Adnan
sumber
Mau memberikan penjelasan?
Leaky Nun
@KennyLau Added
Adnan
1

Python 2, 64 byte

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

Fungsi anonim ini menampilkan daftar pembagi. Pembagi dihitung dengan pembagian percobaan bilangan bulat dalam kisaran [1, ceil(sqrt(n))], yaitu O(sqrt(n)). Jika n % x == 0(setara dengan n%x<1), maka kedua xdan n/xyang pembagi dari n.

Cobalah online

Mego
sumber
1

Jelly , 9 byte

½Rḍ³Tµ³:;

Sebagai jawaban lain, ini adalah O (√n) jika kita membuat asumsi (salah) bahwa pembagian bilangan bulat adalah O (1) .

Bagaimana itu bekerja

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

Cobalah online!

Dennis
sumber
1

Javascript, 47 byte

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

Paulo
sumber
0

Mathematica, 50 byte

Mirip dengan solusi @ flawr .

Melakukan pembagian jejak untuk x dari 1 hingga akar kuadrat dari n dan jika dapat dibagi, menyimpannya ke daftar sebagai x dan n / x .

(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  • Catatan yang membutuhkan 3 byte untuk mewakili dalam UTF-8, membuat string 48 karakter membutuhkan 50 byte dalam representasi UTF-8.

Pemakaian

  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}
mil
sumber
Yah, itu membutuhkan 3 byte ...
Leaky Nun
@ KennyLau Ya, saya salah, seharusnya memeriksa ulang
mil
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]

Saya pikir saya akan menulis versi yang mengembalikan daftar deduplicated yang diurutkan, dan ternyata ternyata 4 byte lebih pendek ...

Neil
sumber
0

C #, 87 byte


Golf

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

Tidak disatukan

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

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

    o += "," + v;

    return o;
}

Kode lengkap

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

Rilis

  • v1.0 - 87 bytes- Solusi awal.

Catatan

  • Dalam kode Golf , saya menggunakan vardan dan intbukannya Stringdan Int32untuk membuat kode lebih pendek, sedangkan dalam Kode Tidak Lengkap dan Kode Lengkap saya menggunakan Stringdan Int32untuk membuat kode lebih mudah dibaca.
auhmaan
sumber
Saya pernah mendengar bahwa forsecara umum lebih baik daripada while.
Leaky Nun
Solusi Anda memiliki kompleksitas O (n), bukan O (sqrt (n)) ...
Leaky Nun
@ KennyLau itu tergantung situasi, dalam hal ini memiliki forloop akan memiliki panjang yang sama dengan whileloop. Dalam hal ini tidak relevan memiliki atau memiliki yang lain.
auhmaan
Tetapi dalam hal ini dapat menghemat satu byte ...
Leaky Nun
0

Lua, 83 byte

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

Sayangnya, saya tidak bisa berbuat lebih baik

pengguna6245072
sumber
1. selamat datang di PPCG, semoga Anda menikmati situs ini! 2. Anda dapat mengubah == 0 ke <1 untuk menghemat beberapa byte. 3. Anda dapat menggunakan struktur ternary alih-alih jika kemudian berakhir, tetapi saya tidak tahu apakah itu akan menghemat byte. 4. Kompleksitas algoritme Anda adalah O (n) yang tidak memenuhi persyaratan.
Leaky Nun
Baiklah. Apakah daftar perlu dipesan, atau diformat dengan tepat?
user6245072
"Daftar keluaran mungkin berisi duplikat. Daftar keluaran tidak perlu disortir."
Leaky Nun
Benar lol. Dan apakah saya perlu mencetak hasil atau array yang berisi itu sudah cukup?
user6245072
Baik, Anda mencetaknya atau mengembalikannya (di dalam fungsi).
Leaky Nun
0

Perl 6 , 40 byte

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

Penjelasan:

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

Pemakaian:

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
sumber
0

c #, 87 byte

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

saya tidak tahu apakah ini bekerja untuk semua angka, saya kira itu berhasil.

tapi kerumitannya benar, jadi itu sudah bukan sesuatu

downrep_nation
sumber
0

Ruby, 56 byte

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

Kode mesin IA-32, 27 byte

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

Kode sumber (sintaks 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;

Parameter pertama ( ecx) adalah pointer ke output, parameter kedua (edx ) adalah angka. Itu tidak menandai akhir output dengan cara apa pun; kita harus mengisi array keluaran dengan nol untuk menemukan akhir daftar.

Program C ++ lengkap yang menggunakan kode ini:

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

Keluaran memiliki beberapa gangguan, meskipun mengikuti spesifikasi (tidak perlu untuk menyortir; tidak perlu untuk keunikan).


Masukan: 69

Keluaran:

69
1
23
3

Pembagi berpasangan.


Input: 100

Keluaran:

100
1
50
2
25
4
20
5
10
10

Untuk kuadrat sempurna, pembagi terakhir adalah keluaran dua kali (itu adalah pasangan dengan dirinya sendiri).


Input: 30

Keluaran:

30
1
15
2
10
3
6
5
5
6

Jika input dekat dengan kuadrat sempurna, pasangan terakhir adalah keluaran dua kali. Itu karena urutan cek dalam loop: pertama, ia memeriksa "sisa = 0" dan output, dan hanya kemudian memeriksa "quotient <divisor" untuk keluar dari loop.

anatolyg
sumber
0

SmileBASIC, 49 byte

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

Menggunakan fakta bahwa D>N/D= D>sqrt(N)untuk bilangan positif

12Me21
sumber
0

C, 87 81 byte

Ditingkatkan oleh @ceilingcat , 81 byte:

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

Cobalah online!


Jawaban asli saya, 87 byte:

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

Kompilasi dengan gcc div.c -o div -lm, dan jalankan dengan ./div <n>.


Bonus: Varian yang lebih pendek dengan kompleksitas waktu O (n) dan hardcoded n(46 byte + panjang n):

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

Sunting: Terima kasih kepada @Sriotchilism O'Zaic karena menunjukkan bahwa input tidak boleh di-hardcode, saya memodifikasi pengiriman utama untuk mengambil input melalui argv.

OverclockedSanic
sumber
1
Apakah ninput? Memasukkan input ke dalam variabel bukan cara yang diterima untuk melakukan input di sini karena sejumlah alasan. Anda dapat melihat lebih lanjut tentang formulir input dan output yang diterima dan tidak diterima di sini: codegolf.meta.stackexchange.com/questions/2447/… . Dan jika Anda ingin tahu tentang bahasa tertentu (misalnya C), Anda dapat melihat di sini: codegolf.meta.stackexchange.com/questions/11924/… .
Ad Hoc Garf Hunter
@ SriotchilismO'Zaic Ya, nadalah input. Saya akan mencoba memodifikasinya sehingga dibutuhkan input dengan cara lain. Terima kasih atas informasinya!
OverclockedSanic
0

APL (NARS), 22 karakter, 44 byte

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

uji:

  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
sumber