Berapa banyak langkah yang dilakukan dari n ke 1 dengan mengurangi pembagi terbesar?

50

Terinspirasi oleh pertanyaan ini di Matematika .


Masalah

Biarkan nmenjadi bilangan alami ≥ 2. Ambil pembagi terbesar n- yang berbeda dari ndirinya sendiri - dan kurangi dari n. Ulangi sampai Anda mendapatkan 1.

Pertanyaan

Berapa banyak langkah yang diperlukan untuk meraih 1angka tertentu n ≥ 2.

Contoh terperinci

Mari n = 30.

Pembagi terbesar:

1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

Dibutuhkan 6 langkah untuk mencapainya 1.

Memasukkan

  • Input adalah bilangan bulat n, di mana n ≥ 2.
  • Program Anda harus mendukung input hingga nilai integer maksimum bahasa.

Keluaran

  • Cukup tampilkan jumlah langkah, seperti 6.
  • Leading / trailing spasi putih atau baris baru baik-baik saja.

Contohnya

f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

Persyaratan

  • Anda bisa mendapatkan input dari STDIN, argumen baris perintah, sebagai parameter fungsi atau dari padanan terdekat.
  • Anda dapat menulis suatu program atau fungsi. Jika ini adalah fungsi anonim, harap sertakan contoh cara memintanya.
  • Ini adalah sehingga jawaban terpendek dalam byte menang.
  • Celah standar tidak diijinkan.

Seri ini dapat ditemukan di OEIS juga: A064097

Logaritma kuasi didefinisikan secara induktif oleh a(1) = 0dan a(p) = 1 + a(p-1)jika padalah prima dan a(n*m) = a(n) + a(m)jika m,n > 1.

masukkan nama pengguna di sini
sumber
mengklarifikasi persyaratan input dalam bahasa dengan bilangan bulat presisi asli arbitrer?
Sparr
@Parr saya akan mengatakan, Anda setidaknya harus mendukung hingga 2^32 - 1. Sisanya terserah Anda dan sistem Anda. Harapan, inilah yang Anda maksud dengan pertanyaan Anda.
masukkan nama pengguna
3
Saya suka bagaimana judulnya merangkum semuanya
Luis Mendo

Jawaban:

20

Jelly , 9 byte

ÆṪÐĿÆFL€S

Cobalah online! atau verifikasi semua kasus uji .

Latar Belakang

Definisi urutan A064097 menyiratkan bahwa

definisi

Dengan formula produk Euler

Formula produk Euler

di mana φ menunjukkan fungsi total Euler dan p bervariasi hanya pada bilangan prima.

Menggabungkan keduanya, kami menyimpulkan properti

properti pertama

di mana ω menunjukkan jumlah faktor prima yang berbeda dari n .

Menerapkan rumus yang dihasilkan k + 1 kali, di mana k cukup besar sehingga φ k + 1 (n) = 1 , kita dapatkan

properti kedua

Dari properti ini, kami memperoleh formula

rumus

di mana persamaan terakhir berlaku karena ω (1) = 0 .

Bagaimana itu bekerja

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.
Dennis
sumber
Nah, itu pendekatan yang super pintar!
Abr001am
15

05AB1E , 13 11 byte

Kode:

[DÒ¦P-¼D#]¾

Penjelasan:

[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Menggunakan pengodean CP-1252 . Cobalah online! .

Adnan
sumber
13
Hapus faktor prima pertama (yang terkecil), untuk mendapatkan produk terbesar Seberapa pintar! :-)
Luis Mendo
Saya mengerti, Anda adalah pengembang bahasa
Sarge Borsch
@SargeBorsch Ya, itu benar :)
Adnan
[¼Ñü-¤ÄD#]¾- Saya hampir memotong satu byte dengan berpasangan, oh well ...
Magic Octopus Mm
-1 byte: [Ð#Ò¦P-¼]¾. Ðlebih baik daripada DD.
Grimmy
11

Pyth, 11 byte

fq1=-Q/QhPQ

Suite uji

Ulangi berulang sampai benar.

Penjelasan:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.
isaacg
sumber
itu trik yang sangat bagus untuk filter.
Maltysen
3
Saya tidak mengerti mengapa ini menghasilkan berapa kali fungsi berjalan. Apakah ini fitur tanpa dokumen f?
corsiKa
@corsiKa ftanpa argumen kedua mengulangi semua bilangan bulat positif mulai dari 1dan mengembalikan nilai pertama yang memberikan true pada pernyataan dalam. Nilai ini kebetulan tidak digunakan dalam program ini, sehingga mengembalikan berapa kali ia berjalan. Bukan tidak berdokumen, hanya ortodoks :) Jika ini membantu, Anda dapat menganggap ini sebagai forloop seperti:for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}
FryAmTheEggman
@corsiKa Didokumentasikan dalam referensi karakter di sisi kanan penerjemah online. Dengan hanya satu argumen ( f <l:T> <none>), fadalah input Pertama di mana A(_)kebenaran berakhir[1, 2, 3, 4...] .
Dennis
Ah saya mengerti sekarang. Menggunakan input itu tetapi tidak pernah menggunakan input dalam perhitungan . Itu menjelaskan komentar @Maltysen dari "itu trik yang sangat bagus" karena Anda hanya peduli dengan jumlah iterasi yang tidak menggunakan hitungan itu di mana pun di filter Anda. Saya suka saat-saat ah-ha !
:)
7

Python 2, 50 49 byte

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

Ini tidak akan menyelesaikan ujian terakhir dalam waktu dekat ...

Atau, inilah 48-byte yang mengembalikan Truebukan 1untuk n=2:

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)
Sp3000
sumber
6

Jelly , 10 byte

ÆfḊPạµÐĿi2

Cobalah online! atau verifikasi sebagian besar kasus uji . Kasing uji terakhir selesai dengan cepat secara lokal.

Bagaimana itu bekerja

ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.
Dennis
sumber
5

Retina , 12

  • 14 byte disimpan berkat @ MartinBüttner
(1 +) (? = \ 1 + $)

Ini mengasumsikan input yang diberikan dalam unary dan output diberikan dalam desimal. Jika ini tidak dapat diterima maka kita dapat melakukan ini selama 6 byte lagi:

Retina , 18

  • 8 byte disimpan berkat @ MartinBüttner
. +
$ *
(1 +) (? = \ 1 + $)

Cobalah online - baris pertama ditambahkan untuk menjalankan semua testcases dalam sekali jalan.

Sayangnya ini menggunakan unary untuk perhitungan, jadi input 2016 155 tidak praktis.

  • Tahap pertama (2 baris) hanya mengubah input desimal menjadi unary sebagai string 1s
  • Tahap kedua (1 baris) menghitung faktor terbesar dari n menggunakan kelompok pencocokan regex dan melihat ke belakang dan secara efektif mengurangi dari n. Regex ini akan cocok sebanyak yang diperlukan untuk mengurangi jumlah sejauh mungkin. Jumlah pertandingan regex akan menjadi jumlah langkah, dan output pada tahap ini.
Trauma Digital
sumber
Saya tidak berpikir Anda membutuhkannya \b.
Martin Ender
Anda dapat menyimpan lebih banyak seperti ini dan secara teknis Anda tidak perlu tahap pertama juga .
Martin Ender
@ MartinBüttner Fantastis! Sangat elegan - terima kasih!
Digital Trauma
5

Pyth - 15 14 13 byte

Casing khusus 1benar-benar membunuh saya.

tl.u-N/Nh+PN2

Cobalah online di sini .

tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1
Maltysen
sumber
1
Satu hal yang saya selalu lupa .... brute force seringkali merupakan pendekatan golf
Leaky Nun
Apa maksudmu dengan casing khusus 1?
Adnan
1
@ Adnan faktorisasi utama 1adalah [], yang menyebabkan kesalahan ketika saya mengambil elemen pertama. Saya harus membuat case khusus untuk membuatnya kembali 1lagi sehingga titik .utetap berakhir. Saya menemukan cara yang lebih baik daripada .xcoba-kecuali yang menyelamatkan saya 2 byte.
Maltysen
Hanya perlu menerima angka> = 2 (> 1).
Solomon Ucko
@SolomonUcko Anda salah paham, titik .utetap pada akhirnya akan mencapai 1semua input, di mana pada titik itu harus dikurung khusus.
Maltysen
5

JavaScript (ES6), * 44 38

Edit 6 byte yang disimpan, terima kasih @ l4m2

(* 4 dipukul masih 4)

Fungsi rekursif

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

Kurang golf

f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

Uji

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
<pre id=O></pre>

edc65
sumber
Bagus, tapi saya pikir Anda harus menghabiskan dua byte yang diperlukan untuk membuat f (1) ==
Neil
@Neil berpikir lagi: tidak. "Biarkan n menjadi bilangan alami ≥ 2 ..."
edc65
Saya butuh kacamata baru.
Neil
Mengapa tidak f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0?
14m2
@ l4m2 benar, mengapa tidak? Terima kasih
edc65
4

Mathematica, 36 byte

f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

Fungsi yang tidak disebutkan namanya membutuhkan byte yang sama:

If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

Ini adalah implementasi definisi yang sangat mudah sebagai fungsi rekursif.

Martin Ender
sumber
4

Oktaf, 59 58 55 byte

function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Diperbarui berkat Stewie Griffin, menghemat 1 byte

Selanjutnya, perbarui tiga byte lagi dengan menggunakan hasil faktorisasi di-cek sementara.

Sampel berjalan:

octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9
dcsohl
sumber
Apakah yang terakhir enddiperlukan dalam oktaf?
Abr001am
Ini. Saya perhatikan itu bukan di matlab dari jawaban Anda, tapi Octave mengharapkannya (seperti yang saya pelajari dari mencoba Anda di Octave).
dcsohl
4

Haskell, 59 byte

f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

Pemakaian:

Prelude> f 30
Prelude> 6

Mungkin sedikit tidak efisien untuk angka besar karena menghasilkan daftar.

Alexandru Dinu
sumber
1
Daftar pemahaman dan <1alih-alih ==0menyimpan beberapa byte: f 1=0;f n=1+f(n-last[a|a<-[1..ndiv2],mod n a<1])
Angs
4

Julia, 56 50 45 39 byte

f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

Ini adalah fungsi rekursif yang menerima integer dan mengembalikan integer.

Tidak Disatukan:

function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

Cobalah online! (termasuk semua kasus uji)

Disimpan 6 byte berkat Martin Büttner dan 11 terima kasih kepada Dennis!

Alex A.
sumber
3

PowerShell v2 +, 81 byte

param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

Terkuat dari kekuatan kasar.

Mengambil input $a, memasukkan satu forlingkaran hingga $akurang dari atau sama dengan 1. Setiap loop kita melewati forloop lain yang menghitung mundur dari $asampai kita menemukan pembagi ( !($a%$i). Paling buruk, kita akan menemukan $i=1sebagai pembagi. Ketika kita melakukannya, tambahkan penghitung kita $j, kurangi pembagi kita $a-=$idan bersiap $i=0untuk keluar dari lingkaran dalam. Akhirnya, kita akan mencapai kondisi di mana loop luar salah (yaitu, $atelah mencapai 1), jadi output $jdan keluar.

Perhatian : Ini akan memakan waktu lama untuk angka yang lebih besar, terutama bilangan prima. Input 100.000.000 memakan waktu ~ 35 detik pada laptop Core i5 saya. Sunting - baru diuji dengan [int]::MaxValue(2 ^ 32-1), dan butuh ~ 27 menit. Tidak terlalu buruk, kurasa.

AdmBorkBork
sumber
3

Matlab, 58 byte

function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end
Abr001am
sumber
3

Japt , 12 byte (tidak bersaing)

@!(UµUk Å×}a

Uji secara online! Non-bersaing karena menggunakan banyak fitur yang ditambahkan jauh setelah tantangan diposting.

Bagaimana itu bekerja

@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

Teknik ini terinspirasi oleh jawaban 05AB1E . Versi sebelumnya digunakan ²¤(tekan 2, potong dua item pertama) Åkarena lebih pendek satu byte dari s1 (perhatikan spasi tambahan); Saya baru menyadari setelah fakta bahwa karena ini menambahkan angka 2 ke akhir array dan irisan dari awal , sebenarnya gagal pada angka komposit ganjil, meskipun ia bekerja pada semua kasus uji yang diberikan.

Produksi ETH
sumber
2

Python 3, 75, 70 , 67 byte.

g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

Ini adalah solusi rekursif yang cukup lurus ke depan. Dibutuhkan waktu yang SANGAT lama untuk kasus uji angka tinggi.

Morgan Thrapp
sumber
2

> <>, 32 byte

<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

Mengharapkan nomor input n,, pada tumpukan.

Program ini membangun urutan lengkap di tumpukan. Karena satu-satunya angka yang dapat mengarah 1adalah 2, membangun urutan berhenti ketika 2tercapai. Ini juga menyebabkan ukuran tumpukan sama dengan jumlah langkah, bukan jumlah langkah +1.

Sok
sumber
2

Ruby, 43 byte

f=->x{x<2?0:1+f[(1..x).find{|i|x%(x-i)<1}]}

Temukan angka terkecil isedemikian sehingga xmembagi x-idan berulang sampai kita mencapai 1.

histokrat
sumber
2

Haskell, 67 byte

Ini kodenya:

a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

Dan inilah salah satu alasan mengapa Haskell luar biasa:

f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

Ya, di Haskell Anda dapat mendefinisikan -->setara dengan ==.

Michael Klein
sumber
2

Matlab, 107 byte

a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))
  • Non-bersaing, ini bukan terjemahan berulang dari kiriman terakhir saya, hanya metode algerbraic langsung lainnya, ini merangkum semua log biner dari semua faktor utama, agak ambigu untuk menggambarkan.
  • Saya akan bermain golf ini lebih banyak ketika saya punya waktu.
Abr001am
sumber
2

MATL, 17 16 byte

`tttYfl)/-tq]vnq

Cobalah secara Online

Penjelasan

        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result
Suever
sumber
2

C99, 62 61 byte

1 byte bermain golf oleh @Alchymist.

f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}  

Panggil sebagai f (x, & y), di mana x adalah input dan y adalah output.

mIllIbyte
sumber
Jika Anda menguji% - b maka Anda dapat menghindari b-- di akhir. Penghematan satu byte secara keseluruhan.
Alchymist
2

Clojure, 116 104 byte

(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 byte dengan memfilter rentang untuk menemukan kelipatan, kemudian menggunakan lastsatu untuk mendapatkan yang terbesar

Solusi naif yang pada dasarnya hanya menyelesaikan masalah seperti yang dijelaskan oleh OP. Sayangnya, menemukan pembagi terbesar saja membutuhkan setengah dari byte yang digunakan. Setidaknya saya harus punya banyak ruang untuk bermain golf dari sini.

Pregolfed dan uji:

(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6
Carcigenicate
sumber
1
@insertusernamehere Tidak, sayangnya, karena itu semua adalah pengidentifikasi yang valid. Saya telah menghapus semua spasi yang mungkin. Jika saya ingin bermain golf lebih jauh, saya harus mengerjakan ulang algoritme.
Carcigenicate
2

Perl 6 , 35 byte

{+({$_ -first $_%%*,[R,] ^$_}...1)}

Cobalah online!

Bagaimana itu bekerja

{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.
seseorang
sumber
1

Pyth, 17 16 byte

L?tbhy-b*F+1tPb0

Cobalah online! (The y.vpada akhirnya adalah untuk pemanggilan fungsi)


17 byte asli:

L?tb+1y-b*F+1tPb0

Cobalah online! (The y.vpada akhirnya adalah untuk pemanggilan fungsi)

(Saya benar-benar menjawab pertanyaan itu dengan program Pyth ini.)

Biarawati Bocor
sumber
Saya sebenarnya tidak repot-repot melalui program Anda, tetapi jika Anda menggunakan definisi rekursif dalam OP, umungkin lebih pendek dari rekursi yang sebenarnya.
Maltysen
1

Pyke, 11 byte (tidak bersaing)

D3Phf-oRr;o

Ini menggunakan perilaku baru di mana jika ada pengecualian yang muncul setelah goto, ia mengembalikan keadaan dari sebelum goto (kecuali definisi variabel) dan berlanjut. Dalam hal ini setara dengan kode python berikut:

# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

Ini semua dimungkinkan menggunakan Pyke tanpa konstruksi loop sementara - yay goto!

Coba di sini!

Biru
sumber
1

JavaScript (ES6), 70 54 byte

f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

Penerapan rumus rekursif yang disediakan, tetapi sekarang diperbarui untuk menggunakan rekursi untuk menemukan pembagi juga.

Neil
sumber
1

Perl, 57 +1 ( -pbendera) = 58 byte

$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Pemakaian:

> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Tidak Disatukan:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}
Denis Ibaev
sumber
1

Clojure, 98 96 byte

#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

gunakan for :whenuntuk menemukan pembagi terbesar, loop sampai tidak ada nilai lebih besar dari yang ditemukan.

NikoNyrh
sumber