Contribution

Un seul entier $1 \leq x \leq 10^{15}$ .

Production

Nombre maximal d'entiers positifs distincts ayant le produit $x$ .

Exemples

Entrée: 1099511627776. Sortie: 9. Une liste optimale possible de facteurs est: (1, 2, 4, 8, 16, 32, 64, 128, 4096).

Entrée: 127381. Sortie 4. Une liste optimale possible de facteurs est la suivante: (1, 17, 59, 127).

Lié à cette vieille question .

code-golf math Anush
la source

9

Pourriez-vous ajouter quelques cas de test supplémentaires? (De préférence de taille raisonnable.)

Arnauld

8

Compte tenu de vos commentaires sur la plupart des réponses: si vous recherchez plutôt du code efficace, cela ne devrait certainement pas être marqué comme code-golf. Vous pouvez envisager soit fastest-codeou fastest-algorithmpour un défi à venir. Si vous vouliez vraiment que toutes les réponses fonctionnent dans un temps limité dans la plage spécifiée, cela aurait dû être explicitement mentionné. (Et j'aurais recommandé une gamme plus petite pour qu'elle n'entre pas en conflit avec code-golfentièrement.)

Arnauld

@Arnauld Non, je fais attention à faire du golf de code et personne n'est jugé pour cela. Ce serait juste cool si le code pouvait s'exécuter pour les plages d'entrée spécifiées.

Anush

5

Citant xnor: Si ce n'est pas obligatoire, les réponses ne le feront pas .

Arnauld

1

Car x=1, 2, ...j'obtiens f(x)=1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 3, 4, 2, 3ce que je ne trouve pas dans OEIS. Il est suffisamment clair que des enregistrements apparaîtront pour les nombres factoriels x. Par exemple le plus petit xqui f(x)=13sera 13!. Je suppose fque cela ne dépend que des exposants de la factorisation principale. Donc, pour trouver, f(13^4*19^7*29^2)nous pourrions simplifier f(2^7*3^4*5^2).

Jeppe Stig Nielsen

5

Wolfram Language (Mathematica) , 52 octets

Max[Length/@Cases[Subsets@Divisors@#,{a__}/;1a==#]]&

Essayez-le en ligne!

4 octets enregistrés grâce à @attinat

Voici également une version de 153 octets qui calcule 1099511627776et10^15

Max[Length/@Table[s=RandomSample@Flatten[Table@@@FactorInteger[#]];Last@Select[Times@@@TakeList[s,#]&/@IntegerPartitions@Length@s,DuplicateFreeQ],5!]]+1&

Essayez-le en ligne!

Le résultat pour 10^15est 12

{1, 2, 4, 5, 10, 16, 25, 40, 50, 100, 125, 250}

J42161217
la source

Crashes avec 1099511627776

Anush

7

@Anush Il ne plante pas. A juste besoin de mémoire. Vous n'avez rien dit sur les limitations de mémoire. Ceci est le code golf

J42161217

Oui je m'en rends compte. Ce serait bien si vous pouviez réellement exécuter le code dans les plages d'entrée spécifiées dans la question.

Anush

6

@Anush C'est du code-golf. Pas de bonnes réponses. Veuillez préciser vos critères. Une réponse est valide ou non. Je pense que le problème ici est la question ... Peut-être que vous devriez le changer en "algorithme le plus suffisant"

J42161217

3

@Anush J'ai fait une modification dans ma réponse et ajouté une autre version qui est vraiment rapide et efficace au cas où vous voudriez la vérifier

J42161217

4

Wolfram Language (Mathematica) , 38 octets

(c=n=#;If[i∣n,n/=i,--c]~Do~{i,n};c)&

Essayez-le en ligne!

Algorithme gourmand. Expire sur TIO sur des entrées plus grandes telles que 1099511627776.

attinat
la source

3

05AB1E , 9 octets

Très inefficace. Expirera sur TIO pour les nombres avec un grand nombre de diviseurs.

ÑæʒPQ}€gZ

Essayez-le en ligne!

Explication

Ñ          # push a list of divisors of the input
 æ         # push the powerset of that list
  ʒPQ}     # filter, keep only the lists whose product is the input
      €g   # get the length of each
        Z  # take the maximum

Emigna
la source

Votre code TIO semble afficher 3 au lieu de 9.

Anush

@Anush: C'est un nombre différent de votre exemple (puisque celui-ci arrive à expiration en raison de nombreux facteurs). Je devrais probablement utiliser un exemple plus distinct.

Emigna

€gZest un peu plus efficace que éθgpour le même bytecount.

Grimmy

@Grimy: Vrai. Cela ne fera pas beaucoup de différence car c'est le filtre qui est le grand méchant ici, mais cela ne fait pas de mal d'être un peu plus efficace :)

Emigna

2

Perl 6 , 38 octets

{$!=$_;+grep {$!%%$_&&($!/=$_)},1..$_}

Essayez-le en ligne!

Adopte l'approche gourmande pour sélectionner les diviseurs.

Jo King
la source

Ne se termine pas par 1099511627776

Anush

6

@Anush Eh bien, cela se termine finalement . Généralement, la réponse est valable si l'algorithme du programme fonctionnerait avec n'importe quelle entrée, si on lui donnait autant de mémoire et de temps qu'il le voulait. Comme il s'agit de code-golf , je l'ai optimisé pour la longueur du code, pas pour la complexité algorithmique

Jo King

2

Javascript (ES6), 39 octets

f=(n,i=0)=>n%++i?n>i&&f(n,i):1+f(n/i,i)

Il y a probablement quelques octets qui peuvent être enregistrés ici et là. Utilise simplement l'algorithme gourmand pour les facteurs.

vrugtehagel
la source

2

Gelée , 9 octets

ŒPP=³ƊƇẈṀ

Essayez-le en ligne!

-1 octet grâce à quelqu'un

-2 octets grâce à ErikTheOutgolfer

HyperNeutrino
la source

Lors de la préparation d'une entrée pour le superseeker OEIS, j'ai créé un programme Jelly golfable probable de 11 octets (qui utilise une approche différente), et il est peu probable que je poste une réponse Jelly, donc je ferai comme si j'avais joué un octet à partir de votre solution: ÆE×8‘½’:2S‘(il fonctionne avec la puissance de la section "formule" OEIS pour A003056). Avertissement: cela peut être faux, mais cela fonctionne sur les cas de test.

mon pronom est monicareinstate

Il ne semble pas se terminer avec 1099511627776

Anush

@someone ne fonctionne pas pendant 36 mais merci

HyperNeutrino

@Anush ouais, c'est vraiment lent parce que je l'ai

joué

1

Vous pouvez supprimer ÆD, ce n'est pas comme s'il y avait plus de partitions qui vont être créées comme ça, ça va juste prendre beaucoup plus de temps (expiration pour

x \geq 21

$x\ge21$ ).

Erik the Outgolfer

2

Japt `-h` , 13 octets

â à f_×¶UÃmÊn

Essayez-le

Incarnation de l'ignorance
la source

2

Brachylog , 8 octets

f;?⟨⊇×⟩l

Essayez-le en ligne!

(L'approche naïve, {~×≠l}ᶠ⌉ génère un nombre infini de solutions avec des 1 supplémentaires avant de les éliminer ≠, et ne parvient donc pas à se terminer. Ce n'est pas un problème, cependant, car c'est pour le même nombre d'octets!)

Prend l'entrée via la variable d'entrée et la sortie via la variable de sortie. L'en-tête sur TIO contient une copie de la plupart du code pour vous montrer quelle est la liste des facteurs, mais cela fonctionne parfaitement sans elle. Puisqu'il ⊇donne d'abord des sous-listes plus grandes, ce prédicat fait essentiellement la même chose que la plupart des autres réponses, mais sans générer et filtrer explicitement l'ensemble complet des facteurs, grâce au retour arrière.

            The output
       l    is the length of
    ⊇       a sublist (the largest satisfying these constraints)
f           of the factors of
            the input
 ; ⟨  ⟩     which
     ×      with its elements multiplied together
  ?         is the input.

Chaîne indépendante
la source

1

Scala , 77 octets

def f(n:Long)={var(m,c,i)=(n,1,2L);while(i<=m){if(m%i==0){m/=i;c+=1};i+=1};c}

Essayez-le en ligne!

Peter
la source

1

Gaia , 10 9 octets

Π=
dz↑⁇(l

Essayez-le en ligne!

Suit le même "algorithme" que celui vu ailleurs - filtrez le jeu de puissance du diviseur le plus longtemps avec un produit égal au nombre et retournez sa longueur.

	| helper function
Π=	| is prod(list)==n (implicit)?
	|
	| main function; implicitly takes n
dz	| divisor powerset (in decreasing order of size)
  ↑⁇	| filter by helper function
    (l	| take the first element and take the length (implicitly output)

Giuseppe
la source

0

Palourde , 15 octets

p}_`nq#:;qQ@s~Q

Lien TIO bientôt disponible (quand dennis se retire)

Fondamentalement, un port de la solution 05AB1E @ Emigna.

Explication

                - Implicit Q = first input
p               - Print...
 }              - The last element of...
  _             - Sorted...
   `nq          - Lengths of... (map q => q.len)
           @s   - Items in powerset of
             ~Q - Proper divisors of Q
      #         - Where... (filter)
        ;q      - Product of subset
       :        - Equals...
          Q     - Q

Skidsdev
la source

0

C # (Visual C # Interactive Compiler) , 54 octets

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

Utilise la même approche que les réponses de @ vrugtehagel et @ JoKing.

Essayez-le en ligne!

Incarnation de l'ignorance
la source

En supposant que j'ai implémenté votre logique correctement, une solution de 53 octets (que je ne pouvais pas me débarrasser du mot-clé "return"): Essayez-le en ligne!

mon pronom est monicareinstate

1

@someone Merci, mais selon la méta, les fonctions doivent être réutilisables . De plus, je ne sais pas s'il est acceptable que des déclarations en dehors de la fonction omettent un point-virgule de fin, peut faire une méta-publication à ce sujet.

Incarnation de l'ignorance

0

Rubis , 34 octets

Expire évidemment sur ce nombre massif, mais finira par expirer si on lui donne suffisamment de temps sur une autre machine.

->n{(1..n).count{|e|n%e<1?n/=e:p}}

Essayez-le en ligne!

Encre de valeur
la source

Un jeu de factorisation

Contribution

Production

Exemples

Réponses:

Wolfram Language (Mathematica) , 52 octets

Wolfram Language (Mathematica) , 38 octets

05AB1E , 9 octets

Perl 6 , 38 octets

Javascript (ES6), 39 octets

Gelée , 9 octets

Japt `-h` , 13 octets

Brachylog , 8 octets

Scala , 77 octets

Gaia , 10 9 octets

Palourde , 15 octets

Explication

C # (Visual C # Interactive Compiler) , 54 octets

Rubis , 34 octets

Un jeu de factorisation

Contribution

Production

Exemples

Réponses:

Wolfram Language (Mathematica) , 52 octets

Wolfram Language (Mathematica) , 38 octets

05AB1E , 9 octets

Perl 6 , 38 octets

Javascript (ES6), 39 octets

Gelée , 9 octets

Japt -h , 13 octets

Brachylog , 8 octets

Scala , 77 octets

Gaia , 10 9 octets

Palourde , 15 octets

Explication

C # (Visual C # Interactive Compiler) , 54 octets

Rubis , 34 octets

Japt `-h` , 13 octets