Prolog (SWI) , 134 128 127 124 octets
Cette réponse fait partie d'une collaboration entre moi et 0 '. Nous avons tous les deux travaillé ensemble, la seule raison pour laquelle je poste c'est parce que j'ai gagné Rock, Paper, Scissors.
\Q-->{Q=1};"(",\N,")",\B,{findnsols(N,I,(between(2,inf,I),\+ (between(3,I,U),0=:=I mod(U-1))),L)->append(_,[Y],L),Q is Y*B}.
Essayez-le en ligne!
Explication
Cette réponse est un parfait exemple de ce qui rend le golf amusant à Prolog.
Cette réponse utilise le système puissant de Prologs pour les grammaires de clauses définies. Voici notre grammaire un peu golfée.
head(1)-->[].
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
prime(N,Y):-
findnsols(N,I,(
between(2,inf,I),
isprime(I)
),L),
append(_,[Y],L),!.
La première règle de construction est:
head(1)-->[].
Cela indique à Prolog que la chaîne vide correspond à 1.
Notre deuxième règle de construction est un peu plus complexe.
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
Cela nous indique que toute chaîne non vide contient des parenthèses autour d'une clause avec ces mêmes règles, à droite d'une clause avec ces mêmes règles.
Il nous indique également que la valeur de cette clause ( Q) suit la règle:
{prime(N,Y),Q is Y*B}
Décomposer cela, Qest le produit de 2 nombres Yet B. Best juste la valeur de la clause à gauche et Yest le Ne premier où Nest la valeur de la clause entre parenthèses.
Cette règle couvre les deux règles de formation de l'arbre des facteurs
- La concaténation se multiplie
- Le boîtier prend le nième premier
Maintenant, pour les définitions de prédicat. Dans la version non golfée, il y a deux prédicats en jeu (dans mon code actuel, j'ai enchaîné les prédicats en avant). Les deux prédicats pertinents ici sont isprime/1, ce qui correspond à un nombre premier, et prime/2, qui, étant donné Net Y, correspond si s Yest le Ne premier. Nous avons d'abord
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
Cela fonctionne d'une définition assez standard de la primalité, nous insistons sur le fait qu'il n'y a pas de nombre entre 2 et I, y compris 2 mais pas Iqui divise I.
Le prochain prédicat est également assez simple
prime(N,Y):-
findnsols(N,I,(
between(2,inf,I),
isprime(I)
),L),
append(_,[Y],L),!.
Nous utilisons findnsolspour trouver les premiers Nnombres premiers, puis nous renvoyons le dernier. L'astuce ici est que même s'il findnsolsn'est pas garanti de trouver les plus petits N nombres premiers, en raison de la façon dont SWI le gère, betweenil trouvera toujours les nombres premiers plus tôt. Cela signifie cependant que nous devons couper pour l'empêcher de trouver plus de nombres premiers.
Les golfs
Nous pouvons transmettre la raison dans notre code deux fois. Puisque isprimen'est utilisé qu'une fois que sa définition peut être déplacée à l'intérieur de prime. La prochaine consiste à se déplacer primedirectement à l'intérieur du DCG, mais comme nous utilisons une coupure primepour éviter findnsolsde produire trop de nombres premiers, nous avons un petit problème. La coupe, coupe tout le DCG au lieu du peu que nous voulons. Après un peu de fouille de documentation, nous avons trouvé que cela once/1pourrait être utilisé pour couper uniquement cette partie mais pas la totalité du DCG. Cependant, un approfondissement de la documentation a révélé que l' ->opérateur pouvait également être utilisé pour effectuer une tâche similaire. L' ->opérateur est à peu près équivalent à ,!,nous avons donc déplacé notre coupe de l'autre côté de append/3et l' avons remplacée par ->.
Dans SWI-Prolog, les prédicats (et règles) peuvent être des opérateurs sous forme de noms, ce qui nous permet de supprimer les parenthèses normalement requises. Ainsi, nous pouvons économiser 6 octets en appelant la règle \.
