Trouver le nombre le plus lisse

59

Votre défi consiste à trouver le nombre le plus fluide sur une plage donnée. En d’autres termes, recherchez le nombre dont le plus grand facteur premier est le plus petit.

Un nombre entier est un nombre dont le plus grand facteur premier est petit. Les nombres de ce type sont utiles pour l'algorithme de transformation rapide de Fourier, l'analyse cryptographique et d'autres applications.

Par exemple, sur l'intervalle 5, 6, 7, 8, 9, 10, 8 est le nombre le plus régulier, car le plus grand facteur premier de 8 est 2, alors que tous les autres nombres ont un facteur premier égal ou supérieur à 3.

Entrée: L'entrée consistera en deux entiers positifs définissant une plage. Le nombre entier minimum autorisé dans la plage est 2. Vous pouvez choisir si la plage est inclusive, exclusive, semi-exclusive, etc., tant qu'une plage arbitraire peut être spécifiée dans les limites de votre langue. Vous pouvez prendre les nombres via une entrée de fonction, stdin, un argument de ligne de commande ou toute autre méthode équivalente pour votre langue. Aucune information supplémentaire d'encodage dans l'entrée.

Sortie: renvoyer, imprimer ou un ou plusieurs équivalents équivalents dans la plage d’entrée qui sont au maximum lisses (facteur le plus grand minimal). Le renvoi de plusieurs résultats est facultatif, mais si vous choisissez de le faire, les résultats doivent être clairement délimités. Le format de sortie natif convient pour plusieurs résultats.

Veuillez indiquer dans votre réponse comment vous prenez et donnez la sortie.

Scoring: code de golf. Compter en caractères si écrit en ASCII, ou 8 * octets / 7 si pas en ASCII.

Cas de test:

Remarque: Il s’agit de plages de style Python, incluant le bas de gamme mais pas le haut de gamme. Changer selon votre programme. Un seul résultat est nécessaire.

smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002
isaacg
la source
Les plages spécifiées comme (début, longueur) au lieu de (début, fin) sont-elles acceptables?
CodesInChaos
1
@CodesInChaos Bien sûr. C'est couvert par la clause "ou autre".
isaacg
3
Je ne vois pas l'intérêt de pénaliser les réponses non-ASCII. Il serait plus simple de simplement compter les octets dans tous les cas.
nyuszika7h
1
@ nyuszika7h Ascii est nettement plus petit qu'un octet - il utilise seulement 7 bits. Par conséquent, je note un caractère sur 7 bits et redimensionne les autres langues en conséquence. Toutefois, si la langue n'est pas ASCII mais peut contenir tous ses caractères sur 7 bits, je n'appliquerai pas le supplément. Voir J ​​/ K contre APL. tl; dr Bytes est plus simple, mais donne APL et. Al. un avantage subtil mais injuste.
isaacg
3
@isaacg, vous encouragez la création de pseudo-langues à l'aide de jeux de caractères plus petits. si nous obtenons des jeux de caractères 7 bits différents des jeux de caractères 8 bits, quelqu'un peut compresser la plupart des langues modernes en 6 bits (64 caractères nous permettent d'obtenir AZ, 0-9, une poignée d'espaces, 20 de ponctuation et quelques-uns de plus) .
Sparr

Réponses:

99

CJam - 13

q~,>{mfW=}$0=

Essayez-le sur http://cjam.aditsu.net/

Exemple d'entrée: 2001 2014
Exemple de sortie:2002

Explication:

q~lit et évalue l'entrée, en poussant les 2 nombres de la pile (disons min et max),
,un tableau [0 1 ... max-1]
>coupe le tableau en commençant à min, ce qui donne [min ... max-1]
{…}$le tableau utilise le bloc pour calculer la clé de tri et
mfobtient un tableau avec tous les facteurs premiers d’un nombre, afin d’
W=obtenir le dernier élément du tableau (W = -1), obtenant ainsi le plus grand facteur premier à utiliser en tant que la clé de tri
0=récupère le premier élément du tableau (trié)

Aditsu
la source
38
Eh bien, je suppose que c'est ça.
Eric Tressler
5
J'ai besoin d'ajouter une fonction factoriser à pyth.
isaacg
6
Cette langue est la magie.
Brobin
8
C’est aussi près de tirer quelques HQ9 + que possible sans devenir une faille. Impressionnant!
Ingo Bürk
25
ل͜ ຈ ༽ ノmfWquelqu'un l'a résolu en 13 caractères.
internets sont faits de chat
66

Regex ( saveur .NET PCRE), 183 129 octets

N'essayez pas ca a la maison!

Ce n'est pas vraiment un candidat à la victoire. Mais Eric Tressler a suggéré de résoudre ce problème avec rien d'autre qu'une regex, et je n'ai pas pu résister à l'idée de tenter le coup. Cela est peut-être aussi possible dans PCRE (et même plus court, voir ci-dessous), mais j’ai choisi .NET car ma solution nécessite des recherches arbitraires. Et c'est parti:

(?<=^(1+),.*)(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((11+)(?=.*(?=\7$)(?!(11+?)\8+$))(?=\7+$)|(?!(11+)\9+$)1+)).*(?=\2$)(?=\6)))1+

L'entrée est codée comme une plage inclusive, séparée par des virgules, où les deux nombres sont donnés en notation unaire à l'aide de 1s. La correspondance sera la fin S1 où Sest le nombre le plus lisse de la plage. Les liens sont brisés en faveur du plus petit nombre.

Ainsi, le deuxième exemple de la question serait la chaîne suivante (correspondance soulignée)

111111111,1111111111111111
                 =========

Il est basé sur la regex à vérification primaire (maintenant assez connue) , dont les variations sont intégrées 6 fois.

Voici une version utilisant des espaces libres et des commentaires pour ceux qui veulent savoir ce qui se passe.

# Note that the beginning of the match we're looking for is somewhere
# in the second part of the input.
(?<=^(1+),.*)          # Pick up the minimum range MIN in group 1
(?=\1)                 # Make sure there are at least MIN 1s ahead

                       # Now there will be N 1s ahead of the cursor
                       # where MIN <= N <= MAX.


(?=(                   # Find the largest prime factor of this number
                       # store it in group 2.
  (11+)                # Capture a potential prime factor P in group 3
  (?=                  # Check that it's prime
    .*(?=\3$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?!(11+?)\4+$)     # Check that the remaining 1s are not composite
  )
  (?=\3+$)             # Now check that P is a divisor of N.
|                      # This does not work for prime N, so we need a 
                       # separate check
  (?!(11+)\5+$)        # Make sure that N is prime.
  1+                   # Match N
))

(?!                    # Now we need to make sure that here is not 
                       # another (smaller) number M with a smaller 
                       # largest prime factor

  .+                   # Backtrack through all remaining positions
  (?=\1)               # Make sure there are still MIN 1s ahead

  (?:
    (?!\2)             # If M is itself less than P we fail 
                       # unconditionally.
  |                    # Else we compare the largest prime factors.
    (?=(               # This is the same as above, but it puts the
                       # prime factor Q in group 6.
      (11+)
      (?=
        .*(?=\7$)
        (?!(11+?)\8+$)
      )
      (?=\7+$)
    |
      (?!(11+)\9+$)
      1+
    ))
    .*(?=\2$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?=\6)             # Try to still match Q (which means that Q is
                       # less than P)
  )
)
1+                     # Grab all digits for the match

Vous pouvez le tester en ligne ici . N'essayez pas trop d'entrées, je ne fais aucune garantie sur les performances de ce monstre.

Modifier:

J'ai fini par le porter sur PCRE (ce qui ne nécessite que deux étapes) et à raccourcir l'expression régulière d'un tiers. Voici la nouvelle version:

^(1+),.*?\K(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((?2))).*(?=\2$)(?=\6)))1+

Ceci est essentiellement le même, avec deux changements:

  • PCRE ne prend pas en charge la recherche de longueur arbitraire (que j'avais l'habitude de placer MINdans le groupe 1). Cependant, PCREprend en charge \Kce qui réinitialise le début de la correspondance à la position actuelle du curseur. Ainsi (?<=^(1+),.*)devient ^(1+),.*?\K, ce qui enregistre déjà deux octets.
  • Les économies réelles proviennent de la fonction de récursivité de PCRE. En réalité, je n'utilise pas de récursivité, mais vous pouvez utiliser (?n)pour faire correspondre le groupe à nnouveau, comme un appel de sous-programme. Étant donné que la regex originale contenait le code permettant de trouver deux fois le plus grand facteur premier d'un nombre, j'ai pu remplacer la majeure partie du second par un simple (?2).
Martin Ender
la source
37
Sainte mère de dieu
Newb
1
@ Timwi Je dois vérifier que le plus grand facteur premier (groupe 3ou 7) est réellement premier. Cela nécessite qu’il y ait une autre copie du facteur après la première capture, ce qui ne serait pas le cas pour les nombres premiers. Bien que je contourne cela dans .NET en plaçant une zone de recherche de telle sorte que je puisse revenir un peu en arrière pour le contrôle, cela ne serait pas possible dans la version PCRE plus courte en raison de l'absence de recherche de longueur variable. Il est probablement possible de raccourcir cette étape, mais je ne pense pas simplement changer +pour que cela *fonctionne.
Martin Ender
2
@MartinEnder Bonjour! J'imagine que vous avez depuis longtemps surmonté ce défi, mais je viens de surfer sur Internet, de voir une solution regex et je ne pouvais m'empêcher d'ignorer totalement votre avertissement au début de ce billet :) Donc, après avoir regardé votre expression rationnelle et être devenu confus, je l'ai essayé à partir de zéro et j'ai trouvé ceci: (.*),.*?\K(?=(..+)((?=((?(R)\6|\2))*$).*(?=\4$)(?!(..+)\5+$)))(?!.+(?=\1)(?=(..+)(?3)).*(?!\2)\6).+ 99 octets en PCRE. De plus, j'ai rencontré beaucoup de votre travail sur ce site et je suis un grand fan: D Dans l'attente d'une bataille de regex dans le futur!
Jaytea
1
Je jouais au code golf avec ce commentaire, je vais donc simplement mettre l'addenda ici: vous pouvez éliminer 4b en \4$éliminant le regard et en le collant après le regard négatif, mais cela a un impact important sur les performances (chaque sous-groupe de chiffres <= \ 4 est vérifié pour la composition plutôt que juste \ 4 lui-même) et échoue sur des entrées plus longues.
Jaytea
1
@ Jaytea Désolé de prendre une éternité pour vous revenir à ce sujet. Depuis que vous avez écrit la chose à partir de zéro, je pense que vous devriez poster une réponse séparée. C'est un bon score et vous méritez le mérite. :)
Martin Ender
16

Regex (saveur PCRE), 66 (65🐌) octets

Inspiré en voyant que Martin Ender et Jaytea , deux génies de regex, ont écrit des solutions de regex à ce code de golf, j'ai écrit le mien à partir de zéro. Le fameux regex Prime-Checking n'apparaît nulle part dans ma solution.

Ne lisez pas ceci si vous ne voulez pas que la magie unaire regex vous soit gâtée. Si vous voulez essayer vous-même de découvrir cette magie, je vous recommande vivement de commencer par résoudre certains problèmes dans la regex ECMAScript:

  1. Faites correspondre les nombres premiers (si vous n'êtes pas déjà habitué à le faire dans regex)
  2. Faites correspondre les pouvoirs de 2 (si vous ne l'avez pas déjà fait). Vous pouvez également vous frayer un chemin dans Regex Golf , qui comprend Prime et Powers. Assurez-vous de faire les ensembles de problèmes Classic et Teukon.
  3. Trouvez le moyen le plus rapide de faire correspondre les puissances de N, où N est une constante (c'est-à-dire spécifiée dans la regex, pas dans l'entrée) qui peut être composite (mais ne doit pas nécessairement l'être). Par exemple, associez des puissances de 6.

  4. Trouvez une façon de faire correspondre les Nièmes puissances, où N est une constante> = 2. Par exemple, faites correspondre les carrés parfaits. (Pour un échauffement, faites correspondre les principaux pouvoirs .)

  5. Faites correspondre les déclarations de multiplication correctes. Correspondre à des nombres triangulaires.

  6. Faites correspondre les chiffres de Fibonacci (si vous êtes aussi fou que moi), ou si vous voulez vous en tenir à quelque chose de plus court, faites correspondre les déclarations d'exonentiation correctes (pour un échauffement, renvoyez en tant que correspondance le logarithme en base 2 d'une puissance de 2 - bonus, faites la même chose pour n’importe quel nombre, en l’arrondissant comme vous le souhaitez) ou en nombres factoriels (pour un échauffement, faites correspondre les nombres premiers ).

  7. Associez des nombres abondants (si vous êtes aussi fou que moi)

  8. Calculer un nombre irrationnel à la précision demandée (par exemple, diviser l’entrée par la racine carrée de 2 et renvoyer le résultat arrondi sous la forme d’une correspondance)

(Le moteur de regex que j'ai écrit peut être utile, car il est très rapide avec les expressions rationnelles mathématiques unaires et inclut un mode numérique unaire qui permet de tester les plages de nombres naturels (mais également un mode chaînes permettant d'évaluer des expressions rationnelles non unaires Par défaut, il est compatible ECMAScript, mais comporte des extensions facultatives (qui peuvent ajouter de manière sélective des sous-ensembles de PCRE, ou même une apparence moléculaire, quelque chose qu'aucun autre moteur d'expression rationnelle n'a).)

Sinon, lisez la suite et lisez également ce GitHub Gist (avertissement, de nombreux spoilers) qui décrit le parcours consistant à pousser la regex ECMAScript à s’attaquer aux fonctions des nombres naturels de difficulté croissante (à commencer par les énigmes de teukon, qui ne sont pas toutes mathématiques, ce qui a déclenché cette périple).

Comme avec les autres solutions regex à ce problème, l'entrée est donnée sous forme de deux nombres dans unary bijective, séparés par une virgule, représentant une plage inclusive. Un seul numéro est renvoyé. L'expression rationnelle peut être modifiée pour renvoyer tous les nombres partageant le même plus petit facteur premier, sous forme de correspondances distinctes, mais cela nécessiterait une recherche de longueur variable et une mise \Ken attente ou un résultat renvoyé sous forme de capture au lieu d'une correspondance.

La technique utilisée ici de division implicite répétée par le plus petit facteur premier est identique à celle utilisée dans les chaînes de correspondance dont la longueur est une quatrième réponse puissante que j'ai postée il y a quelque temps.

Sans plus tarder: ((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$

Vous pouvez l'essayer ici.

Et la version à espace libre, avec des commentaires:

                        # No ^ anchor needed, because this algorithm always returns a
                        # match for valid input (in which the first number is less than
                        # or equal to the second number), and even in /g mode only one
                        # match can be returned. You can add an anchor to make it reject
                        # invalid ranges.

((.+).*),               # \1 = low end of range; \2 = conjectured number that is the
                        # smallest number in the set of the largest prime factor of each
                        # number in the range; note, it is only in subsequent tests that
                        # this is implicitly confined to being prime.
                        # We shall do the rest of our work inside the "high end of range"
                        # number.

(?!                     # Assert that there is no number in the range whose largest prime
                        # factor is smaller than \2.
  .*(?=\1)              # Cycle tail through all numbers in the range, starting with \1.

  (                     # Subroutine (?3):
                        # Find the largest prime factor of tail, and leave it in tail.
                        # It will both be evaluated here as-is, and later as an atomic
                        # subroutine call. As used here, it is not wrapped in an atomic
                        # group. Thus after the return from group 3, backtracking back
                        # into it can increase the value of tail – but this won't mess
                        # with the final result, because only making tail smaller could
                        # change a non-match into a match.

    (                   # Repeatedly divide tail by its smallest prime factor, leaving
                        # only the largest prime factor at the end.

      (?=(..+)(\5+$))   # \6 = tool to make tail = \5 = largest nontrivial factor of
                        # current tail, which is implicitly the result of dividing it
                        # by its smallest prime factor.
      \6                # tail = \5
    )*
  )
  (?!\2)                # matches iff tail < \ 2
)

# now, pick a number in the range whose largest prime factor is \2
.*(?=\1)                # Cycle tail through all numbers in the range, starting with \1.
\K                      # Set us up to return tail as the match.
(?3)                    # tail = largest prime factor of tail
\2$                     # Match iff tail == \2, then return the number whose largest
                        # prime factor is \2 as the match.

L'algorithme peut être facilement porté sur ECMAScript en remplaçant l'appel de sous-routine par une copie du sous-routine et en renvoyant la correspondance en tant que groupe de capture au lieu d'utiliser \ K. Le résultat est 80 octets de longueur:

((x+)x*),(?!.*(?=\1)((?=(xx+)(\4+$))\5)*(?!\2)).*(?=\1)(((?=(xx+)(\8+$))\9)*\2$)

Essayez-le en ligne!

Notez que vous ((.+).*)pouvez modifier cette option en ((.+)+)supprimant la taille d'1 octet (de 66 à 65 octets ) sans perte de la fonctionnalité correcte - mais l'expression régulière explose de manière exponentielle par lenteur.

Essayez-le en ligne! (Version 79 octets ECMAScript à ralentissement exponentiel)

Deadcode
la source
11

Python 2, 95

i=input()
for a in range(*i):
 s=a;p=2
 while~-a:b=a%p<1;p+=1-b;a/=p**b
 if p<i:i=p;j=s                                        
print j

Trouve la régularité des nombres par division d’essai jusqu’à ce que le nombre soit égal à 1. istocke la plus petite régularité jusqu’à présent, jmémorise le nombre qui a donné cette régularité.

Merci à @xnor pour les golfs.

isaacg
la source
1
Cela if/elsedoit être raccourci. Ma première pensée est b=a%p<1;p+=1-b;a/=p**b. Ou un exec qui exécute l'un des deux dans une chaîne entrelacée. En outre, peut-être while~-afonctionne.
xnor
isaacg - j'adore cette réponse! Quelle manière brillante vous avez trouvé de rechercher le plus grand facteur premier! J'ai mis à jour ma réponse pour emprunter votre méthode, avec un crédit pour vous sur la méthode.
Todd Lehman
Excellente solution! En utilisant s,p=a,2, i,j=p,s@ idées de XNOR, la suppression indentation redondante et de mettre le tout en bloc en un rendement en ligne 95 caractères. Vous ne savez pas comment vous en êtes arrivé à 98 ...
Falko
ce code est plein d'émoticônes, :)
Rosenthal
@Falko ces deux modifications n'enregistrent aucun caractère. 7-> 7.
isaacg
10

J, 22 20 19 caractères

({.@/:{:@q:)@(}.i.)

Par exemple

   2001 ({.@/: {:@q:)@(}. i.) 2014
2002

(Les fonctions prenant deux arguments sont infixes dans J.)

Luciole
la source
J'ai également eu une fissure, ne l'ai pas eu aussi court que cette réponse Toujours:(#~ (= <./)@:(i:"1&1)@:*@:(_&q:))@:([ + i.@-~)
mardi
Voici {:le même que >./et enregistre 1 octet.
randomra
@randomra Vous avez raison - bon appel!
FireFly
Magnifique. TIO si vous souhaitez l’ajouter: essayez-le en ligne!
Jonah
9

Haskell, 96 94 93 86 80 caractères

x%y|x<2=y|mod x y<1=div x y%y|0<1=x%(y+1)
a#b=snd$minimum$map(\x->(x%2,x))[a..b]

utilisation via GHCi (une coque Haskell):

>5 # 9
8
>9 # 15
9

EDIT: maintenant un algorithme beaucoup plus simple.

cette solution inclut les deux nombres dans la plage (donc 8 # 9et 7 # 8sont tous les deux 8)

explication:

la fonction (%) prend deux paramètres, x et y. quand y vaut 2, la fonction retourne la finesse de x.

L'algorithme à partir d'ici est simple - obtenez la liste combinée de toutes les limites des nombres dans l'entrée avec chaque régularité stockant une référence à son numéro d'origine, triez-la ensuite pour obtenir le plus petit et renvoyez le numéro référencé.


Voici une version javascript non-golfée avec le même algorithme:

function smoothness(n,p)
{
    p = p || 2
    if (x == 1)
        return p
    if (x % p == 0)
        return smoothness(x/p, p)
    else
        return smoothness(x,p+1);
}
function smoothnessRange(a, b)
{
    var minSmoothness = smoothness(a);
    var min=a;
    for(var i=a+1;i <= b;i++)
        if(minSmoothness > smoothness(i))
        {
            minSmoothness = smoothness(i)
            min = i
        }
    return min;
}
fier haskeller
la source
Serait-il possible d'alias minimum à quelque chose de plus court? Cela semble sauver quelques personnages.
isaacg
J'ai essayé, mais à cause de la restriction du monomorphisme, cela coûte un personnage
fier haskeller
Vous ne pouvez pas simplement faire m = minimum? Haskell est toujours un mystère.
isaacg
1
@isaacg Pour contourner la restriction du monomorphisme, il faudrait écrirem l=minimum l
fier haskeller
2
J'allais publier une solution Haskell, jusqu'à ce que je voie la vôtre, qui bat même ma version incomplète ... +1
nyuszika7h
9

Mathematica, 61 45 39 caractères

Range@##~MinimalBy~Last@*FactorInteger&

Implémentation très simple de la spécification en tant que fonction non nommée.

  • Obtenez la gamme (inclus).
  • Factor tous les entiers.
  • Trouvez le minimum, trié par le plus grand facteur premier.
Martin Ender
la source
8

Lua - 166 caractères

Je n'ai pas (encore!) Assez de réputation pour commenter la solution d'AndoDaan , mais voici quelques améliorations sur son code

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d<1 do f[#f+1]=d n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Changements :

  • Le n%d==0par n%d<1qui est équivalent dans ce cas
  • Supprimé un espace
  • Remplacé table.insert(f,d)par f[#f+1]=d ( #fest le nombre d'éléments de f)
Adriweb
la source
Ah, content d'avoir jeté un coup d'oeil ici. Ah, j'aurais dû vérifier et attraper les deux premiers, mais votre troisième amélioration est nouvelle pour moi (je veux dire tout simplement différente de ce à quoi je suis habitué). Cela va beaucoup m'aider ici et sur golf.shinh.com. Merci!
AndoDaan
8

Bash + coreutils, 56 octets

seq $@|factor|sed 's/:.* / /'|sort -nk2|sed '1s/ .*//;q'

L'entrée provient de exactement deux arguments en ligne de commande (Merci @ nyuszika7h !!!). La sortie est un résultat singulier imprimé sur STDOUT.

  • seq fournit la plage de nombres, un par ligne, à partir des arguments de la ligne de commande.
  • factorlit ces nombres et affiche chaque nombre suivi de deux points et de la liste triée des facteurs premiers de ce nombre. Donc, le plus grand facteur premier est à la fin de chaque ligne.
  • Le premier sedsupprime les deux points et tous les facteurs sauf le dernier / le plus grand facteur, laissant ainsi une liste de chaque nombre (colonne 1) et de son plus grand facteur premier (colonne 2).
  • sort numériquement dans l'ordre croissant de la colonne 2.
  • La sedligne finale correspond à la ligne 1 (numéro dont le plus grand facteur premier est le plus petit de la liste), supprime tout, y compris et après le premier espace, puis se ferme. sedimprime automatiquement le résultat de cette substitution avant de quitter.

Sortie:

$ ./smooth.sh 9 15
12
$ ./smooth.sh 9 16
16
$ ./smooth.sh 157 249
162
$ ./smooth.sh 2001 2014
2002
$ 

Les plages de notes dans ce contexte incluent les deux extrémités.

Trauma numérique
la source
1
seq $@est plus court de 3 octets, si vous pouvez supposer qu’il n’ya que deux arguments.
nyuszika7h
@ nyuszika7h Belle idée - merci!
Digital Trauma
5

Python 2, 67

f=lambda R,F=1,i=2:[n for n in range(*R)if F**n%n<1]or f(R,F*i,i+1)

Penser à un autre golf m'a donné l'idée d'un nouvel algorithme pour vérifier la fluidité, d'où la réponse tardive.

La factorisation en facteurs de la factorielle i!comprend exactement les nombres premiers au plus i. Donc, si nest un produit de nombres premiers distincts, sa douceur (le plus grand facteur premier) est le plus petit ipour lequel nest un diviseur de i!. Pour tenir compte de facteurs premiers répétés n, nous pouvons utiliser une puissance de suffisamment élevée i!. En particulier, (i!)**nsuffit.

Le code tente d'augmenter les factorielles F=i!, mises à jour récursivement. Nous filtrons pour les diviseurs de Fdans la plage d'entrée et les sortons s'il y en a, et sinon nous passons à (i+1)!.

Cas de test:

>> f([157, 249])
[162, 192, 216, 243]
Xnor
la source
4

C,  149   95

Réponse modifiée:

Je ne peux pas demander de crédit pour cette solution. Cette réponse mise à jour reprend la belle méthode utilisée par isaacg dans sa solution Python. Je voulais voir s'il était possible d'écrire en C comme imbriquée for/ whileboucle sans accolades, et il est!

R(a,b,n,q,p,m){for(;a<b;m=p<q?a:m,q=p<q?p:q,n=++a,p=2)while(n>1)if(n%p)p++;else n/=p;return m;}

Explication:

  • Fonction R(a,b,n,q,p,m)balaie la plage aà b-1et retourne le premier numéro trouvé plus doux. Exige le respect de l' invocation sous la forme suivante: R(a,b,a,b,2,0)afin que les variables sont effectivement initialisés dans la fonction comme suit: n=a;q=b;p=2;m=0;.

Réponse originale :

C'était ma réponse originale ...

P(n,f,p){for(;++f<n;)p=p&&n%f;return p;}
G(n,f){for(;--f>1;)if(n%f==0&&P(f,1,1))return f;}
R(a,b,p,n){for(;++p;)for(n=a;n<b;n++)if(G(n,n)==p)return n;}

Explication:

  • Function P(n,f,p)teste la valeur npour la primalité et renvoie true (différent de zéro) si nprime ou faux (zéro) si nnon premier. fet pdoit être passé comme 1.
  • Function G(n,f)renvoie le plus grand facteur premier de n. fdoit être passé comme n.
  • Fonction R(a,b,p,n)balaie la plage aà b-1et retourne le premier numéro trouvé plus doux. pdoit être passé en tant que 1. npeut être n'importe quelle valeur.

Pilote d'essai:

test(a,b){printf("smooth_range(%d, %d)\n%d\n",a,b,S(a,b,1,0));}
main(){test(5,11);test(9,16);test(9,17);test(157,249);test(2001,2014);}

Sortie:

smooth_range(5, 11)
8
smooth_range(9, 16)
9
smooth_range(9, 17)
16
smooth_range(157, 249)
162
smooth_range(2001, 2014)
2002
Todd Lehman
la source
Je dirais que cela tombe sous le coup de la clause "Pas d’information supplémentaire dans la saisie".
Alchymist
@Alchymist - Vous avez peut-être raison ... mais je ne pense pas que les pseudo-arguments contiennent des informations supplémentaires. Du moins, aucune information ne permet de déterminer la réponse.
Todd Lehman
4

Haskell - 120

import Data.List
import Data.Ord
x!y=(minimumBy(comparing(%2)))[x..y]
x%y|x<y=y|x`mod`y==0=(x`div`y)%y|otherwise=x%(y+1)

Exemple d'utilisation:

> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002
Taylor Fausak
la source
1
Ne pourriez-vous pas utiliser <1au lieu de ==0?
Dfeuer
Oui, ce serait une belle amélioration. Il y a beaucoup de petites choses qui pourraient être mieux faites. Heureusement, cette réponse les concerne déjà tous: codegolf.stackexchange.com/a/36461
Taylor Fausak
4

Q, 91 caractères K, 78 caractères

{(x+{where x=min x}{(-2#{x div 2+(where 0=x mod 2_til x)@0}\[{x>0};x])@0}'[(x)_til y+1])@0}

k raserait probablement une douzaine de personnages

edit: en effet, traiter la limite supérieure comme non inclusive cette fois

{*:x+{&:x=min x}{*:-2#{6h$x%2+*:&:x={y*6h$x%y}[x]'[2_!x]}\[{x>0};x]}'[(x)_!y]}
Arthur B
la source
4

Remarque: cette réponse n'est pas autorisée.

Cette réponse utilise plusieurs fonctionnalités de Pyth ajoutées après la demande du défi.

J'ai ajouté une autre nouvelle fonctionnalité, appelant range unary sur un tuple à 2 éléments, ce qui raccourcit la solution de deux caractères:

Pyth , 7

hoePNUQ

L'entrée est maintenant prise séparée par des virgules. Le reste est le même.


Cette réponse utilise une fonctionnalité de Pyth qui a été ajoutée après la réponse à cette question, en particulier après avoir consulté la merveilleuse solution CJam de @ aditsu. Cela étant dit, je voulais montrer ce que l'ajout de cette fonctionnalité a rendu possible. La fonction est P, qui est une fonction arity-1 qui, en entrée entière, renvoie une liste de tous les facteurs premiers de l'entrée, triés du plus petit au plus grand.

Pyth , 9

hoePNrQvw

Utilise des plages de style Python, les nouvelles lignes séparées sur STDIN. Génère la plus petite solution dans STDOUT.

Explication:

      Q = eval(input())                         Implicit, because Q is present.
h     head(                                     First element of
 o         order_by(                            Sort, using lambda expression as key.
                    lambda N:                   Implicit in o
  e                          end(               Last element of
   PN                            pfact(N)),     List containing all prime factors of N.
  r                 range(                      Python-style range, lower inc, upper exc.
   Q                      Q,                    A variable, initialized as shown above.
   vw                     eval(input()))))      The second entry of the range, same way.

Tests:

$ newline='
'

$ echo "9${newline}16" | ./pyth.py -c 'hoePNrQvw'
9

$ echo "9${newline}17" | ./pyth.py -c 'hoePNrQvw'
16

$ echo "157${newline}249" | ./pyth.py -c 'hoePNrQvw'
162

$ echo "2001${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002
isaacg
la source
@ MartinBüttner Yep, comme suggéré par son commentaire sur la solution
CJam
@ MartinBüttner Ouais, P, est la nouvelle fonctionnalité. Je vais mettre ça dans la réponse.
isaacg
1
Autorisé ou non, non seulement je l'aime bien, mais je pense aussi que ces "macros" courtes sont lisibles si vous y prêtez attention - elles sont converties en Python, après tout. Quelque chose doit être dit pour une langue de golf qui est bonne pour le golf mais pas nécessairement obscurcissante.
Kuba Ober
@ KubaOber Merci, Kuba. Cela a toujours été mon intention en écrivant Pyth, de le rendre aussi golfé et lisible que possible. Je suis content que ça marche.
isaacg
3

Lua - 176 personnages

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d==0 do table.insert(f, d)n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Je devrais vraiment arrêter de jouer au golf à Lua. Il est inutile.

AndoDaan
la source
14
À mon humble avis, le code de golf est comme la boxe: il existe des classes de poids. Une langue donnée ne gagne peut-être pas directement, mais c'est amusant et éclairant de jouer au golf dans cette classe / cette langue.
Michael Easter
3

Clojure - 173 170 caractères

Je suis un novice Clojure. Golfé:

(defn g[x,d](if(and(= 0(mod x d))(.isProbablePrime(biginteger d) 1))d 0))(defn f[i](apply max-key(partial g i)(range 2(inc i))))(defn s[a,b](first(sort-by f(range a b))))

Échantillons:

Les plages comprennent bas de gamme, excluent haut de gamme: [a, b) N'imprime que l'un des nombres les plus lisses, si plusieurs se produisent.

(println (s 5 11))
(println (s 9 16))
(println (s 9 17))
(println (s 157, 249))
(println (s 2001, 2014))

rendements:

bash$ java -jar clojure-1.6.0.jar range.clj
8
9
16
192
2002

Ungolfed:

(defn g [x,d] (if (and (= 0(mod x d)) (.isProbablePrime (biginteger d) 1)) d 0))
(defn f [i] (apply max-key (partial g i) (range 2 (inc i))))
(defn s [a,b] (first (sort-by f (range a b))))
Michael Easter
la source
1
Une plage incluant le bas de gamme et excluant le haut de gamme est généralement écrite [a, b).
murgatroid99
oui, merci pour la note
Michael Easter,
3

Ruby, 65 62

require'prime'
s=->a,b{(a..b).min_by{|x|x.prime_division[-1]}}

Veuillez nous excuser auprès de https://codegolf.stackexchange.com/a/36484/6828 , il s’agit de la version avec golf (et légèrement simplifiée) de celle. Utilise une plage inclusive puisqu'il s'agit d'un caractère plus court.

1.9.3-p327 :004 > s[157,249]
 => 192 
1.9.3-p327 :005 > s[5,11]
 => 8 
1.9.3-p327 :006 > s[9,15]
 => 12 
1.9.3-p327 :007 > s[9,16]
 => 16 

Et merci à YenTheFirst pour avoir sauvé trois personnages.

histocrate
la source
1
Vous pouvez réellement vous en sortir sans le [0], car la comparaison par tableau donnera quand même la priorité au premier élément. Cela donnera des résultats différents, mais toujours corrects.
YenTheFirst
3

C # LINQ: 317 303 289 262

using System.Linq;class P{static void Main(string[]a){System.Console.Write(Enumerable.Range(int.Parse(a[0]),int.Parse(a[1])).Select(i=>new{i,F=F(i)}).Aggregate((i,j)=>i.F<j.F?i:j).i);}static int F(int a){int b=1;for(;a>1;)if(a%++b<1)while(a%b<1)a/=b;return b;}}

Ungolfed:

using System.Linq;

class P
{
  static void Main(string[]a)
  {
    System.Console.Write(
      Enumerable.Range(int.Parse(a[0]), int.Parse(a[1])) //create an enumerable of numbers containing our range (start, length)
        .Select(i => new { i, F = F(i) }) //make a sort of key value pair, with the key (i) being the number in question and the value (F) being the lowest prime factor
        .Aggregate((i, j) => i.F < j.F ? i : j).i); //somehow sort the array, I'm still not entirely sure how this works
  }
  static int F(int a)
  {
    int b=1;
    for(;a>1;)
      if(a%++b<1)
        while(a%b<1)
          a/=b;
    return b;
  }
}

Il prend au début et la longueur de la ligne de commande et renverra le plus grand nombre lisse.

J'ai utilisé les réponses d' ici et ici pour faire ma réponse.

Merci à VisualMelon pour l’avoir peaufiné et avoir rasé 12 octets! Je me suis également débarrassé des accolades dans la sauvegarde de 2 octets si, et CodeInChaos a souligné certaines choses évidentes que j'ai manquées (merci encore).

ldam
la source
Couple de petites choses d'usage général, vous pouvez économiser 4 octets en Fdéfinissant à int bcôté de m. Dans quelques endroits où vous effectuez la comparaison a%b==0, et aet bsont toujours positifs que vous pouvez couper un octet pour chaque en vérifiant si elle est inférieure à 1 a%b<1. Vous pouvez également enregistrer un octet en incrémentant bla condition if a%++b<0plutôt que dans le for en l'initialisant à 1. Je pense aussi que dans ce cas il est moins cher de simplement qualifier complètement System.Console.WriteLineet d'éviter la namespaceclause.
VisualMelon
@VisualMelon Merci, mis à jour avec vos idées :)
ldam
Le m=...:m;truc tombe en dehors de la boucle while. Par conséquent, vous pouvez supprimer le m=0,et remplacer return m;par return m=b>m?b:m;. Ensuite, vous pouvez laisser tomber m=...:m;entièrement.
tomsmeding
Cela peut sembler bizarre, mais c'est pour moi - moins redable que CJam et J. Je suppose que C # a été conçu pour être verbeux, et que des tentatives pour le rendre moins, le rendre illisible? Hmm ....
Kuba Ober
Non, je suis d'accord, LINQ ressemble à un démon quand on le voit ici et là et qu'on ne joue jamais avec soi-même. Une fois que vous l'aurez compris, c'est vraiment cool :) Cela dit, je ne comprends toujours pas comment ça Aggregatemarche, je l'ai juste essayé après l'avoir vue dans une autre réponse pour obtenir mon nouvel objet au lieu d'un seul champ à l'intérieur, et il est juste arrivé de fonctionner parfaitement :)
ldam
2

R, 83

library(gmp)
n=a:b
n[which.min(lapply(lapply(lapply(n,factorize),max),as.numeric))]

où le bas de la plage d'entrée est assigné aet le haut (inclusif) est assigné b.

gmpest un package disponible sur CRAN. J'avais l'impression d'être sale jusqu'à ce que je voie cette mffonction absurde dans CJam. Installez en tapant install.packages("gmp")dans la console.

shadowtalker
la source
1
Si vous utilisez lapply3 fois, vous voudrez peut-être l'aliaser (c. l=lapply-à- d. , Puis utiliser l(...). De même, factorizeétant la seule fonction que vous utilisez depuis un package, gmpvous pouvez utiliser gmp::factorizeau lieu de charger la bibliothèque, puis d’utiliser factorize. Votre code deviendrait donc ce l=lapply;n=a:b;n[which.min(l(l(l(n,gmp::factorize),max),as.numeric))]qui est de 69 octets.
Plannapus
2

PowerShell - 85

($args[0]..$args[1]|sort{$d=2
while($_-gt1){while(!($_%$d)){$m=$d;$_/=$d}$d++}$m})[0]

Cela va trier une plage de nombres (inclus) en fonction du facteur premier maximum de chaque nombre. Il retourne l'élément trié le plus bas.

> smooth 5 10
8
> smooth 9 15
12
> smooth 9 16
16
> smooth 157 248
243
> smooth 2001 2013
2002
Rynant
la source
2

J - 16 caractères

Utilisation du style de plage ( début , longueur ), comme le permettent les commentaires.

(0{+/:{:@q:@+)i.

Pour être utilisé comme verbe dyadique: l'argument gauche est début , droite est longueur .

   5 (+)i. 6              NB. range
5 6 7 8 9 10
   5 (q:@+)i. 6           NB. prime factorizations
5 0 0
2 3 0
7 0 0
2 2 2
3 3 0
2 5 0
   5 ({:@q:@+)i. 6        NB. largest prime factors
5 3 7 2 3 5
   5 (+/:{:@q:@+)i. 6     NB. sort range by smallest factors
8 6 9 5 10 7
   5 (0{+/:{:@q:@+)i. 6   NB. take first entry
8
   f=:(0{+/:{:@q:@+)i.    NB. can also be named
   2001 f 13
2002

Une solution ( début , fin ) a +2 caractères et exclut la fin; y compris la fin est +2 de plus. Mais du côté positif, cela semble plutôt agréable puisque nous associons tous les {accolades}.

(0{}./:{:@q:@}.)i.    NB. excluding
(0{}./:{:@q:@}.)1+i.  NB. including
algorithmeshark
la source
2

Sérieusement, 8 * 14/7 = 16 (non compétitif)

,x;`yM`M;m@í@E

Seriously a été créé après ce défi, mais je voulais poster cette réponse car elle illustre bien le type de défis que Sérieusement réussit.

Essayez-le en ligne!

Explication:

,x;`yM`M;m@í@E
,x;             make two copies of range(a,b) (a,b = input())
   `  `M;       make two copies of the result of the map:
    yM            push maximum prime factor
         m@í    push index of minimum element from prime factors
            @E  push element from range with given index
Mego
la source
2

Pyth , 7 octets

.mePbrF

Essayez-le ici!

[a,b)[a,b]}r

.mePbrF – Full program with arguments a and b.
     rF – Fold by half-inclusive range. Yields the integers in [a, b).
.m      – Values b in that list which give minimal results when applied f.
  ePb   – function / block f. 
   Pb   – Prime factors of b.
  e     – Last element. This is guaranteed to yield the largest, as they're sorted.
M. Xcoder
la source
1

Cobra - 150

def f(r as vari int)
    x,y=r
    c,o=y,0
    for n in x:y,for m in n:0:-1
        p=1
        for l in 2:m,if m%l<1,p=0
        if n%m<=0<p
            if m<c,c,o=m,n
            break
    print o

Je ne sais même pas pourquoi je me suis inquiété, le cobra ne peut tout simplement pas rivaliser ici.

Οurous
la source
1
Cobra semble identique au python ... Quelles sont les différences?
Beta Decay
@BetaDecay Cobra est ce qui se passe lorsque vous donnez à C # la syntaxe de Python. The Cobra Website
Οurous
1

Ruby - 113 caractères

Utiliser stdlib. Renvoie un résultat. Testé sur rubis 2.1.2.

require 'prime'
def smooth_range(a,b)
  (a...b).sort_by{|e|e.prime_division.flat_map{|f,p|[f]*p}.uniq.max}[0]
end
John P. Terry
la source
1
Bienvenue dans Programmation Puzzles et Code Golf Stack Exchange. Merci d'avoir posté votre résultat. Puisqu'il s'agit d'une question code-golf, veuillez inclure le nombre de vos personnages dans votre réponse. Vous pouvez utiliser un outil tel que celui-ci: javascriptkit.com/script/script2/charcount.shtml
isaacg
1

Perl (5.10+), 83

for(<>..<>){$n=$_;$p=2;$_%$p&&$p++or$_/=$p while$_>1;$m=$p,$r=$n if$p<$m||!$m}
say$r

(le saut de ligne peut être supprimé). Prend deux extrémités d’une plage inclusive sur deux lignes de stdin (car <>c’est moins cher que d’accéder ARGV) et génère le résultat le plus régulier sur stdout. S'il y a une égalité pour le plus lisse, imprime le plus petit. Pourrait imprimer le plus grand au prix d'un caractère.

L'algorithme est fondamentalement le moyen utilisé par isaacg pour trouver le plus grand facteur premier, bien que nous l'ayons développé indépendamment. Cette partie résume à merveille avec une seule déclaration en perl, le reste en a plus que ce que je voudrais bien.

Devrait être exécuté sous perl -Eou avec un use 5.012préambule. Si vous ne pouvez pas faire cela, remplacez say$rpar print$r,$/.

Hobbs
la source
1

Python 2 (84)

f=lambda n,p=2:n>1and f(n/p**(n%p<1),p+(n%p>0))or p
print min(range(*input()),key=f)

La solution de @ isaacg , mais avec une minclé de fonction by à la place de min- find explicite, et une fonction récursive jouant le rôle de l'itération.

Exécutez-vous en Stackless Python pour éviter les limites de récursivité.

Il semble inutile d’utiliser la condition entre parenthèses (n%p<1), puis de répéter sa négation également entre parenthèses (n%p>0), mais c’est le meilleur que j’ai eu. J'ai essayé beaucoup de choses, mais elles ont empiré.

f(n/p**(n%p<1),p+(n%p>0))     # Current for comparison
f(*[n/p,n,p,p+1][n%p>0::2])
n%p and f(n,p+1)or f(n/p,p)
f(*n%p and[n,p+1]or[n/p,p])

Je me félicite de toute amélioration que vous pouvez penser.

Xnor
la source
1

Java 8 - 422 454 caractères

J'apprenais Java 8 et je voulais donner à cette image un coup de projecteur par rapport à Java (ou même aux flux Java 8).

Comparé à d’autres langues, c’est un exercice brutal mais intéressant.

Golfé:

import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}

Ungolfed:

import java.util.stream.*;
import java.math.*;

class F {
    int v;
    int i;
    public int getV() { return v; }
    F (int i) { 
        this.i = i;
        v = IntStream.range(2,i+1)
                     .map( j -> ((i%j==0) && 
                           new BigInteger(""+j).isProbablePrime(1))?j:0)
                     .max()
                     .getAsInt();
    }
}

public class T {
    int s(int a, int b) {
        return IntStream.range(a,b+1)
                    .boxed()
                    .map(F::new)
                    .sorted(java.util.Comparator.comparingInt(F::getV))
                    .collect(java.util.stream.Collectors.toList())
                    .get(0).i;
    }
}

exemple exécuté en utilisant:

public static void main(String[] s) {
    System.out.println(new T().s(157,249));
}

192
Michael Easter
la source
1

MATL ( non compétitif ), 20 octets

Ce langage a été conçu après le challenge

La plage est inclusive aux deux extrémités. Les nombres sont pris comme deux entrées séparées.

2$:t[]w"@YfX>v]4#X<)

Essayez-le en ligne!

Explication

2$:          % implicitly input two numbers. Inclusive range
t            % duplicate                      
[]           % empty array
w            % swap elements in stack         
"            % for each                  
  @          %   push loop variable
  Yf         %   prime factors                  
  X>         %   maximum value
  v          %   vertical concatenation         
]            % end for each                         
4#X<         % arg min 
)            % index with this arg min into initial range of numbers
Luis Mendo
la source
Je suppose qu'aujourd'hui, ce serait 17 octets &:[]y"@YfX>h]&X<)ou peut-être 16 :[]y"@YfX>h]&X<). Le &était vraiment une bonne idée (et je devine yétait pas en arrière disponible alors?).
dimanche
Et il semblerait que la diffusion Yfde préfixes 1 aurait été utile ici aussi, mais ce n'est probablement pas suffisant pour décider que c'est une bonne idée en général. :)
dimanche
Oui, c'était le tout début, alors non you &. Merci à Suever pour la sémantique très utile de ce dernier (mon idée initiale était de faire en sorte que cela signifie "une entrée de plus que la valeur par défaut"). Si nous voyons de plus en plus de cas où, Yfavec l'ajout de ceux-ci, il serait utile d'ajouter cette fonctionnalité. Le problème, c'est qu'il y a environ 34 réponses qui utilisent Yf(selon ce script ), donc c'est difficile à dire
Luis Mendo
1

Gelée , 7 octets, score = 7 ÷ 7 × 8 = 8, défi linguistique suivant

rÆfṀ$ÐṂ

Essayez-le en ligne!

Prend les points d'extrémité inférieur et supérieur comme deux arguments séparés. Affiche une liste de tous les nombres les plus lisses de la plage. (Cela peut être considéré comme une fonction, auquel cas la sortie est une liste de gelée, ou comme un programme complet, auquel cas la sortie utilise la même représentation de liste que JSON.)

Explication

Ces moments où votre programme Jelly n'est qu'une traduction littérale de la spécification…

rÆfṀ$ÐṂ
r        Range from {first argument} to {second argument}
     ÐṂ  Return the elements which have the minimum
   Ṁ$      largest
 Æf          prime factor

la source