Urutkan pembagi angka berdasarkan faktorisasi utama

23

Diberikan input bilangan bulat ≥ 2, mengeluarkan daftar pembagi yang diurutkan berdasarkan eksponen dalam faktorisasi utama mereka, dalam urutan naik, memesan pertama dengan prime terbesar, kemudian oleh terbesar kedua, dan seterusnya.

Sebagai contoh, ambil bilangan bulat 72, yaitu 2 3 3 2 . Ini memiliki pembagi

1     3^0 · 2^0
2     3^0 · 2^1
3     3^1 · 2^0
4     3^0 · 2^2
6     3^1 · 2^1
8     3^0 · 2^3
9     3^2 · 2^0
12    3^1 · 2^2
18    3^2 · 2^1
24    3^1 · 2^3
36    3^2 · 2^2
72    3^2 · 2^3

Ketika diurutkan dalam urutan menaik oleh eksponen pada faktor prima, dengan bilangan prima yang lebih besar yang diprioritaskan, ini menjadi

1     3^0 · 2^0
2     3^0 · 2^1
4     3^0 · 2^2
8     3^0 · 2^3
3     3^1 · 2^0
6     3^1 · 2^1
12    3^1 · 2^2
24    3^1 · 2^3
9     3^2 · 2^0
18    3^2 · 2^1
36    3^2 · 2^2
72    3^2 · 2^3

Perhatikan bahwa daftar ini disortir terlebih dahulu dengan urutan eksponen 3, dan kemudian oleh eksponen 2. Anda juga dapat menganggap ini sebagai bacaan dari kiri ke kanan dan atas ke bawah melintasi kisi-kisi berikut:

        2^0  2^1  2^2  2^3

3^0     1    2    4    8
3^1     3    6    12   24
3^2     9    18   36   72

Kasus uji:

2 => 1 2
72 => 1 2 4 8 3 6 12 24 9 18 36 72
101 => 1 101
360 => 1 2 4 8 3 6 12 24 9 18 36 72 5 10 20 40 15 30 60 120 45 90 180 360
3780 => 1 2 4 3 6 12 9 18 36 27 54 108 5 10 20 15 30 60 45 90 180 135 270 540 7 14 28 21 42 84 63 126 252 189 378 756 35 70 140 105 210 420 315 630 1260 945 1890 3780
30030 => 1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210 11 22 33 66 55 110 165 330 77 154 231 462 385 770 1155 2310 13 26 39 78 65 130 195 390 91 182 273 546 455 910 1365 2730 143 286 429 858 715 1430 2145 4290 1001 2002 3003 6006 5005 10010 15015 30030
65536 => 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
74088 => 1 2 4 8 3 6 12 24 9 18 36 72 27 54 108 216 7 14 28 56 21 42 84 168 63 126 252 504 189 378 756 1512 49 98 196 392 147 294 588 1176 441 882 1764 3528 1323 2646 5292 10584 343 686 1372 2744 1029 2058 4116 8232 3087 6174 12348 24696 9261 18522 37044 74088

Karena ini adalah , kode terpendek dalam byte akan menang.

Gagang pintu
sumber

Jawaban:

8

05AB1E , 6 byte

Kode:

ÑÒí{€P

Penjelasan:

Ñ       # Get the divisors of input.
 Ò      # Factorize each.
  í     # Reverse each.
   {    # Sort the array.
    €P  # Product each.

Menggunakan pengkodean CP-1252 . Cobalah online! .

Adnan
sumber
1
Noice: p (bagus sekali)
framp
8

Jelly , 8 7 byte

ÆDÆfU$Þ

Cobalah online! Terima kasih kepada @ Dennis untuk -1 byte.

ÆD         Array of divisors, e.g. 24 -> [1, 2, 4, 8, 3, 6, 12, 24]
      Þ    Sort by...
     $       Combine previous two links...
  Æf           Factorise each, e.g. ['', [2], [3], [2, 2], [2, 3], [2, 2, 2],
                   [2, 2, 3], [2, 2, 2, 3]]
    U          Upend/reverse each sublist
Sp3000
sumber
2
ÆDÆfU$Þ(menggunakan sort-by Jelly baru), menyimpan satu byte.
Dennis
7

Pyth, 10 byte

+1{*Mt_DyP

Cobalah online: Demonstrasi

Sayangnya produk di atas daftar kosong tidak didefinisikan sebagai 1 dalam Pyth. Ini biaya tiga byte tambahan.

Penjelasan:

+1{*Mt_DyPQ   implicit Q (=input number) at the end
         PQ   prime factorization of input
        y     powerset
      _D      order by reversed subsets
     t        remove the empy subset
   *M         compute the product of each subsets
  {           remove duplicates
+1            prepend 1
Jakube
sumber
7

Jelly , 12 10 byte

2 byte terima kasih kepada @ Sp3000.

ÆE'ḶUṚŒpUṚÆẸ
ÆEU'ḶŒpUÆẸ

Cobalah online!

Suite uji.

ÆE            Array of exponents, e.g. 24 -> [3, 1] since 24 = 2^3*3^1
  U           Upend/reverse, e.g. [1, 3]
   ‘Ḷ         Range of each, from 0, e.g. [[0, 1], [0, 1, 2, 3]]
     Œp       Cartesian product, e.g. [[0, 0], [0, 1], ..., [1, 3]]
       U      Upend, reversing the innermost lists
        ÆẸ    Inverse of ÆE, converting exponents back into a number

Kredit ke @ Sp3000 untuk muncul dengan format penjelasan.

Biarawati Bocor
sumber
7

Python 2, 85 byte

n=input()
p,=L=[1]
while~-n:
 l=L;p+=1
 while n%p<1:L=l+[x*p for x in L];n/=p
print L

Tidak ada faktorisasi, tidak ada penyortiran. Implementasi rekursif yang sama panjangnya:

f=lambda n,p=2:1/n*[1]or n%p and f(n,p+1)or[x*c for x in f(n/p)for c in[1,p][x%p<1:]]
Tidak
sumber
5

Sebenarnya, 19 byte

;÷#o♂w♂RS`"iⁿ"£Mπ`M

Cobalah online!

Penjelasan:

;÷#o♂w♂RS`"iⁿ"£Mπ`M
;                    duplicate input
 ÷                   divisors
  #o                 include input in divisors list (note to self: fix this bug)
    ♂w               factor each integer into a list of [prime, exponent] pairs
      ♂R             reverse each list, so that the largest prime comes first
        S            sort the list
         `"iⁿ"£Mπ`M  for each factorization:
          "iⁿ"£M       for each [prime, exponent] pair:
           iⁿ            push prime**exponent
                π      product
Mego
sumber
5

JavaScript, 78 byte

f=(n,p=2,a=[1],b=a)=>n<2?a:n%p?f(n,p+1,a):f(n/p,p,a.concat(b=b.map(m=>m*p)),b)

Berdasarkan ide @ xnor, walaupun saya tidak mengerti kodenya, jadi saya harus mengimplementasikannya kembali dari awal. Algoritma dasarnya adalah bahwa Anda mulai dengan [1] dan kalikan dengan [1, ..., pᵏ] untuk setiap pᵏ dalam factorisation utama n, meskipun karena saya tidak memiliki factorisation prima atau produk kartesius saya harus melakukannya semua secara rekursif. Contoh:

n=72 p=2 a=[1] b=[1]
n=36 p=2 a=[1,2] b=[2]
n=18 p=2 a=[1,2,4] b=[4]
 n=9 p=2 a=[1,2,4,8] b=[8]
 n=9 p=3 a=[1,2,4,8] b=[1,2,4,8]
 n=3 p=3 a=[1,2,4,8,3,6,12,24] b=[3,6,12,24]
 n=1 p=3 a=[1,2,4,8,3,6,12,24,9,18,36,72] b=[9,18,36,72]
Neil
sumber
Baru ingat ketika Anda berada di 10k .. sekarang hampir 14k. Teruskan!!
NiCk Newman
2

R, 196 byte

n=scan()
if(n<4)c(1,n)else{
r=2:n
d=NULL
while(n>1){i=r[min(which(n%%r==0))];d=c(d,i);n=n/i}
m=unique(d)
b=table(d)
l=list()
for(i in 1:length(m))l[[i]]=m[i]^(0:b[i])
apply(expand.grid(l),1,prod)}

Ini akan menjadi tidak efisien sebagai heck karena saya tidak tahan godaan untuk menggunakan library(primes). Ini menciptakan vektor ddari semua faktor utama input, menghitung frekuensinya (jumlah kejadian), dan kemudian menghitung produk kartesius dari semua kekuatan yang mungkin (dari 0 hingga frekuensi masing-masing b[i]), yang digunakan prodfungsi tersebut. Sial, kasus spesial 2 dan 3! Kalau tidak, ini adalah showcase yang bagus dari penanganan dataframe R dan fungsi vektor / operasi baris (dan bahkan tablefungsi statistik murni !).

Tentu saja, efisiensinya dapat ditingkatkan dengan biaya 15 byte menggunakan r=2:ceiling(sqrt(n)), jika seseorang peduli. Berikut ini adalah versi tanpa bulu yang lebih baik:

factorise <- function(n){
  if (n<4) c(1,n) else { # Now that all special cases have been handled
    r=2:ceiling(sqrt(n)) # We check all divisors smaller than the square root
    d=NULL # Initiate the variable for divisors
    while (n>1) {
      i=r[min(which(n%%r==0))] # Check the first divisor with a zero remainder
      d=c(d,i) # Append it to the list of divisors
      n=n/i   # Divide by it and check again
    }
    m=unique(d) # Get unique divisors, and they are already sorted
    b=table(d) # Count their frequencies
    l=list() # Initiate a list of all possible powers of unique factors
    for(i in 1:length(m)) l[[i]]=m[i]^(0:b[i]) # Calculate powers
    apply(expand.grid(l),1,prod) # Make a cartesian dataframe and row-multiply
  }
}
Andreï Kostyrka
sumber
2

Mathematica 150 byte

f[t_]:=Thread@{#,IntegerExponent[t,#]&/@#}&@Prime@Range@PrimePi@Max@FactorInteger[t][[All,1]];Times@@@(#^#2&@@@#&/@Sort[Reverse/@(f@#&/@Divisors@#)])&
martin
sumber
2

Brachylog , 3 byte

fḋᵒ

Cobalah online!

Kode membaca kurang lebih sama seperti judul tantangan: "faktor-faktor input, diurutkan berdasarkan dekomposisi utama mereka". Memastikan bahwa kecantikan 3-byte ini benar-benar lulus uji kasus dengan hanya menggunakan pengertian bawaan Brachylog tentang cara menyortir daftar yang mengharuskan saya untuk menyalin dan menempelkan semua nomor itu ke Clojure REPL, di mana elemen daftar dipisahkan oleh spasi dan koma adalah spasi putih, tetapi ternyata memang berfungsi.

String yang tidak terkait
sumber
2

APL (Dyalog Extended) , 17 byte

Terima kasih banyak kepada ngn dan Adm atas bantuan mereka dalam bermain golf kedua program APL ini di The APL Orchard , tempat yang tepat untuk mempelajari APL dan mendapatkan bantuan APL.

∊×⍀/⌽{⊂×\1,⍵}⌸⍨⍭⎕

Cobalah online!

Tidak melakukanolf

∊×⍀/⌽{⊂×\1,⍵}⌸⍨⍭⎕

                  Gets evaluated input from stdin.
                  Gives us a list of the prime factors of our input.
                   Example for 720: 2 2 2 2 3 3 5
     {      }⌸⍨     groups our prime factors by the keys in the left argument,
                   and  passes the prime factors as both arguments,
                   grouping all the identical primes together
                   before running a {} dfn on them
      ⊂×\1,⍵       We append 1 to each group, get a list of powers of each prime,
                   and enclose the groups to remove 0s from uneven rows.
                 This reverses the prime power groups.
 ×⍀/              This multiplies all the powers together into
                   a matrix of the divisors of our input.
                   (Same as ∘.×/ in Dyalog Unicode)
                  And this turns the matrix into 
                   a list of divisors sorted by prime factorization.
                   We print implicitly, and we're done.

APL (Dyalog Unicode) , 29 byte SBCS

{∊∘.×/⌽{⊂×\1,⍵}⌸⍨¯2÷/∪∧\⍵∨⍳⍵}

Cobalah online!

Tidak melakukanolf

{∊∘.×/⌽{⊂×\1,⍵}⌸⍨¯2÷/∪∧\⍵∨⍳⍵}

{                           }  A dfn, a function in brackets.
                        ⍵∨⍳⍵   We take the GCD of our input with 
                               all the numbers in range(1, input).
                     ∪∧\       This returns all the unique LCMs of
                               every prefix of our list of GCDs.
                               Example for 72: 1 2 6 12 24 72.
                 ¯2÷/          We divide pairwise (and in reverse)
                               by using a filter window of negative two 2).
                               Example for 72: 2 3 2 2 3, our prime factors.
       {      }⌸⍨               groups our prime factors by the keys in the left argument,
                               and  passes the prime factors as both arguments,
                               grouping all the identical primes together
                               before running a {} dfn on them
           1,⍵                 We append 1 to each group.
        ⊂×\                    Then we get a list of powers of each prime,
                               and enclose the groups to remove 0s from uneven rows.
                              This reverses the prime power groups.
  ∘.×/                         This multiplies all the powers together into 
                               a matrix of the divisors of our input.
                              And this turns the matrix into a list of divisors
                               sorted by prime factorization.
                               We return implicitly, and we're done.
Sherlock9
sumber
1

J, 32 31 byte

[:(*/@#~>:#:[:i.[:*/>:)&|./2&p:

Raih daftar bilangan prima dan eksponen integer input, balikkan masing-masing, dan susun pembagi darinya.

Pemakaian

   f =: [:(*/@#~>:#:[:i.[:*/>:)&|./2&p:
   f 2
1 2
   f 72
1 2 4 8 3 6 12 24 9 18 36 72
   f 101
1 101

Penjelasan

[:(*/@#~>:#:[:i.[:*/>:)&|./2&p:  Input: n
                           2&p:  Factor n as a list where the first row are the primes
                                 and the second are their exponents
[:                     &|./      Reverse each list
                    >:           Increment each exponent by 1
                [:*/             Reduce it using multiplication
            [:i.                 Construct a range from 0 to that product exclusive
        >:                       The list of each exponent incremented
          #:                     Reduce each number in the previous range as a mixed base
                                 using the incremented exponents
      #~                         For each mixed base value in that range, copy from
                                 the list of primes that many times
   */@                           Reduce the copied primes using multiplication
                                 Return this list of products as the result
mil
sumber
1

Ruby, 71 byte

Jawaban ini didasarkan pada jawaban Python 2 xnor.

->n{a,=t=[1];(s=t;a+=1;(t=s+t.map{|z|z*a};n/=a)while n%a<1)while n>1;t}

Alternatif dengan panjang yang sama adalah:

->n{a,=t=[1];(a+=1;(t+=t.map{|z|z*a};n/=a)while n%a<1)while n>1;t.uniq}

Tidak melakukan pelanggaran:

def f(num)
  factor = 1
  list = [1]
  while num != 1
    s = list
    factor += 1
    while num % factor == 0
      list = s + list.map{|z| z*factor}
      num /= factor
    end
  end
  return list
end

def g(num)
  factor = 1
  list = [1]
  while num != 1
    factor += 1
    while num % factor == 0
      list += list.map{|z| z*factor}
      num /= factor
    end
  end
  return list.uniq
end
Sherlock9
sumber
1

Japt , 12 9 byte

â mk ñÔ®×

-3 byte terima kasih kepada @Shaggy

Cobalah online!

Quintec
sumber
Ini harus bekerja selama 9 byte.
Shaggy
@Shaggy Oh yeah, lupa fungsi sederhana harus didefinisikan seperti itu, meskipun saya hanya menyarankannya untuk lol ASCII saja
Quintec
0

Mathematica, 56 byte

1##&@@@Tuples@Reverse[#^Range[0,#2]&@@@FactorInteger@#]&
alephalpha
sumber