Un diviseur d'un nombre n est un nombre qui divise également n , y compris 1 et n lui-même. Le nombre de diviseurs d (n) est le nombre de diviseurs d'un nombre. Voici d (n) pour le premier couple n:

n    divisors    d(n)
1    1           1
2    1, 2        2
3    1, 3        2
4    1, 2, 4     3
5    1, 5        2
6    1, 2, 3, 6  4

Nous pouvons soustraire à plusieurs reprises le nombre de diviseurs d'un nombre. Par exemple:

16                  = 16
16 - d(16) = 16 - 5 = 11
11 - d(11) = 11 - 2 = 9
 9 - d( 9) =  9 - 3 = 6
 6 - d( 6) =  6 - 4 = 2
 2 - d( 2) =  2 - 2 = 0

Dans ce cas, il a fallu 5 étapes pour arriver à 0.

Écrivez un programme ou une fonction qui, étant donné un nombre non négatif n, renvoie le nombre d'étapes nécessaires pour le réduire à 0 par soustraction répétée du nombre de diviseurs.

Exemples:

0, 0
1, 1
6, 2
16, 5
100, 19
100000, 7534

Gelée, 10 9 octets

1 octet merci à Dennis ♦ .

Port de ma réponse en Pyth .

ÆDLạµÐĿL’

Essayez-le en ligne!

Suite de tests.

Explication

_ÆDL$$ÐĿL’
      ÐĿ    Repeat the following until result no longer unique:
 ÆD             Yield the array of the divisors
   L            Yield the length of the array
_               Subtract that from the number
        L   Number of iterations
         ’  Minus one.

Python, 49 octets

f=lambda n:n and-~f(sum(n%~x<0for x in range(n)))

orlp a aidé à sauver un octet! Et Sp3000 en a économisé deux autres. Merci!

C, 52 octets

g,o;l(f){for(g=o=f;o;f%o--||--g);return f?1+l(g):0;}

Pyth, 10 octets

tl.ulf%NTS

Suite de tests.

Explication

tl.ulf%NTS
tl.ulf%NTSNQ  implicit variables at the end
           Q  obtain the input number
  .u      N   repeat the following until result no longer unique:
         S        generate range from 1 to N
     f            filter for:
      %NT             T in that range, which N%T is truthy (not zero)
    l             length of that list
                  that means, we found the number of "non-divisors" of N
tl            number of iterations, minus 1.

Julia, 31 octets

f(n)=n<1?0:f(sum(n%(1:n).>0))+1

Implémentation récursive simple.

MATL , 14 octets

`t~?x@q.]t:\zT

Essayez-le en ligne!

Explication

`            T  % Infinite loop
 t~?    ]       % Duplicate number. Is it non-zero?
    x@q.        % If so: delete number, push iteration index minus 1, break loop
         t:\    % Duplicate, range, modulo (remainder). Divisors give a 0 remainder
            z   % Number of non-zero elements; that is, of non-divisors

JavaScript (ES6), 64 51 octets

f=n=>n&&[...Array(m=n)].map((_,i)=>m-=n%++i<1)|f(m)+1

Ne me demandez pas pourquoi j'utilisais inutilement la récursivité de la queue.

Java, 147 93

a->{int k,i,n=new Integer(a),l=0;for(;n!=0;n-=k)for(l+=k=i=1;i<n;)if(n%i++==0)++k;return l;}

05AB1E, 12 10 octets

Code:

[Ð>#Ñg-¼]¾

Explication:

[           # start infinite loop
 Ð          # triplicate current number
  >#        # increase by 1 and break if true
    Ñg      # get number of divisors
      -     # subtract number of divisors from number
       ¼    # increase counter
        ]   # end loop
         ¾  # print counter

Essayez-le en ligne

Edit: 2 octets enregistrés et un bug avec l'entrée 0 corrigé grâce à @Adnan

R, 50 octets

Mise en œuvre assez simple. Essayez-le en ligne

z=scan();i=0;while(z>0){z=z-sum(z%%1:z<1);i=i+1};i

Mathcad, [tbd] octets

Le schéma d'équivalence d'octets Mathcad reste à déterminer. En utilisant une équivalence approximative, le programme utilise environ 39 "octets". Notez que les opérateurs while et for programmer ne prennent qu'une seule opération de clavier chacun pour entrer (ctl-] et ctl-shft- #, respectivement) - en effet, ils ne peuvent être entrés de cette façon qu'à partir du clavier.

Ce que vous voyez est exactement ce qui est inscrit sur une feuille de calcul Mathcad. Mathcad évalue les équations / programmes et place la sortie sur la même feuille (par exemple, après l'opérateur d'évaluation «=» ou sur le graphique).

MATL, 13 octets

tX`t:\ztt]Nq&

Essayez-le en ligne

Explication:

t               % Duplicate input
 X`      ]      % while loop, consumes 1 input
   t:\z         % calculates n-d(n), by counting number non-divisors
       tt       % dupe twice, for while loop condition, next iteration and to keep in stack
          Nq&   % get stack size, decrement, display that value

Mathematica, 35 octets

If[#<1,0,#0[#-0~DivisorSigma~#]+1]&

Faire usage du bon vieux DivisorSigma. @ MartinBüttner note les alternatives suivantes:

If[#<1,0,#0[#-DivisorSum[#,1&]]+1]&
f@0=0;f@n_:=f[n-DivisorSum[n,1&]]+1

Hoon , 93 76 octets

|=
r/@
?~
r
0
+($(r (sub r (lent (skim (gulf 1^r) |=(@ =(0 (mod r +<))))))))

Non golfé:

|=  r/@
?~  r
  0
=+  (skim (gulf 1^r) |=(@ =(0 (mod r +<))))
+($(r (sub r (lent -))))

Renvoie une fonction qui prend un atome, r. Créez une valeur intermédiaire qui contient tous les estimateurs de r(Make list [1..n], ne gardez que les éléments où (mod ri) ​​== 0). Si rest zéro retourne zéro, sinon retourne la valeur incrémentée de récursivité avec r égal r- (diviseurs de longueur).

Le code tel quel prend un temps stupide à évaluer pour n = 100 000, entièrement parce que trouver les auteurs de devis pour les grands nombres fait une liste géante et les cartographie. La mémorisation des diviseurs obtient la sortie correcte pour n = 10 000, mais je n'ai pas pris la peine d'attendre 100 000

Haskell, 43 40 39 octets

g 0=0;g n=1+g(sum$min 1.mod n<$>[1..n])

Approche récursive simple. Exemple d'utilisation: g 16-> 5.

Modifier: @Lynn a enregistré 3 4 octets. Merci!

PowerShell v2 +, 74 67 octets

param($n)for($o=0;$n-gt0){$a=0;1..$n|%{$a+=!($n%$_)};$n-=$a;$o++}$o

Semble assez long par rapport à certaines des autres réponses ...

Prend une entrée $n, entre dans une forboucle avec une condition $nsupérieure à 0. Pour chaque itération de boucle, nous définissons helper $a, puis parcourons chaque numéro de 1à $n. Chaque boucle interne est vérifiée par rapport à chaque nombre pour voir s'il s'agit d'un diviseur, et si c'est le cas, nous incrémentons notre aide $a(en utilisant la négation booléenne et le transtypage implicite en entier). Ensuite, nous soustrayons le nombre de diviseurs que nous avons trouvés $n-=$aet incrémentons notre compteur $o++. Enfin, nous sortons $o.

Prend beaucoup de temps à exécuter, car c'est une construction significative pour la boucle. Par exemple, l'exécution n = 10,000sur ma machine (ancien Core i5 d'un an) prend presque 3 minutes.

Raquette - 126 octets jusqu'à 98 octets 91 octets

Une solution extrêmement naïve - pourrait probablement être réduite beaucoup avec un algorithme décent et quelques astuces lisp que je ne connais pas

(define(g x[c 0][d 0][i 2])(cond[(= x 0)c][(= i x)(g d(+ 1 c))][(=(modulo x i)0)(g x c d(+ 1 i))][else(g x c(+ 1 d)(+ 1 i))]))

Edit: explication sur demande. Comme je l'ai dit, il s'agit d'une solution récursive extrêmement naïve et peut être beaucoup plus courte.

(define (g x [c 0] [d 0] [i 2]) ;g is the name of the function - arguments are x (input), c (counter for steps), d (non-divisor counter), i (iterator)
  (cond
    [(= x 0) c] ;once x gets to 0 c is outputted
    [(= i x) (g d (+ 1 c))] ;if iterator reaches x then we recurse with d as input and add 1 to c
    [(= (modulo x i) 0) (g x c d (+ 1 i))] ;checks if iterator is non divisor, then adds it to d and increments iterator
    [else(g x c (+ 1 d) (+ 1 i))])) ;otherwise just increments iterator

Modifier la version 2: 98 octets avec un algorithme moins stupide (toujours assez stupide et peut être plus court)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(cdr(build-list x values))))))))

Explication:

(define (g x) ;function name g, input x
  (if (< x 1)
      0 ;returns 0 if x < 1 (base case)
      (+ 1 ;simple recursion - adds 1 to output for each time we're looping
         (g (length ;the input we're passing is the length of... 
              (filter (λ (y) (> (modulo x y) 0)) ;the list where all numbers which are 0 modulo x are 0 are filtered out from...
                             (cdr (build-list x values)))))))) ;the list of all integers up to x, not including 0

Edit 3: 7 octets enregistrés en remplaçant (cdr(build-list x values))par(build-list x add1)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(build-list x add1)))))))

> <> , 52 + 2 = 54 octets

Le numéro d'entrée doit être présent sur la pile au démarrage du programme, il y a donc +2 octets pour l' -vindicateur. Essayez-le en ligne!

:0)?v~ln;>~$-]
03[}\::
@@:$<    v?=0:-1}+{~$?@@01%@:

4 octets gênants gaspillés sur des problèmes d'alignement. Bah.

Celui-ci fonctionne en construisant la séquence de nà 0sur la pile. Une fois que 0 a été atteint, éclatez-le et sortez la longueur de la pile restante.

Soit dit en passant, il fonctionne dans le O(n^2)temps, donc je n'essaierais pas n = 100000...

> <> , 36 + 3 = 39 octets

:?v~ln; >~&
:}\0&
+&>1-:?!^:{:}$%0)&

L'implémentation est relativement simple, chaque itération étant sum(n%k>0 for k in range(1,n-1)). +3 octets pour l' -vindicateur, par méta .

Essayez-le en ligne!

Rubis, 42 octets

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

Il y a une erreur de débordement de pile sur le plus grand cas de test 100000, voici donc une version itérative dans les 49 octets . Cela prend un certain temps, compte tenu de la O(N^2)complexité.

->n{c=0;c+=1 while 0<n-=(1..n).count{|i|n%i<1};c}

Perl 5, 40 octets

sub f{@_?(1,f((1)x grep@_%$_,1..@_)):()}

L'entrée et la sortie sont des listes du nombre requis de copies de 1.

C #, 63 octets

int F(int n)=>n<1?0:F(Enumerable.Range(1,n).Count(i=>n%i>0))+1;

En fait, 17 octets

";╗R`╜%`░l;"£╬klD

Essayez-le en ligne! (remarque: le dernier cas de test arrive à expiration sur TIO)

Explication:

";╗R`╜%`░l;"£╬klD
"          "£╬     while top of stack is truthy, call the function:
 ;╗                  push a copy of n to reg0
   R                 range(1,n+1) ([1,n])
    `  `░l             push the number of values where the following is truthy:
     ╜%                  k mod n
                       (this computes the number of non-divisors of n)
          ;            make a copy
              klD  push entire stack as list, count number of items, subtract 1
                   (the result is the number of times the function was called)