Étant donné deux entiers positifs A et B , renvoyez la position p qui minimise le nombre de facteurs premiers (comptage des multiplicités) de l'entier résultant, lorsque B est inséré dans A en p .

Par exemple, étant donné A = 1234 et B = 32 , ce sont les insertions possibles (avec p étant indexé 0) et les informations correspondantes sur leurs facteurs premiers:

p | Résultat | Facteurs premiers | Ω (N) / Nombre

0 | 321234 | [2, 3, 37, 1447] | 4
1 | 132234 | [2, 3, 22039] | 3
2 | 123234 | [2, 3, 19, 23, 47] | 5
3 | 123324 | [2, 2, 3, 43, 239] | 5
4 | 123432 | [2, 2, 2, 3, 37, 139] | 6

Vous pouvez voir que le résultat a un nombre minimal de facteurs premiers, 3, lorsque p vaut 1. Donc, dans ce cas particulier, vous devez sortir 1 .

Spécifications

S'il existe plusieurs positions p qui minimisent le résultat, vous pouvez choisir de les afficher toutes ou l'une d'entre elles.
Vous pouvez choisir l'indexation 0 ou l'indexation 1 pour p , mais ce choix doit être cohérent.
A et B peuvent être considérés comme des entiers, des chaînes ou des listes de chiffres.
Vous pouvez concurrencer dans n'importe quel langage de programmation et pouvez prendre des entrées et fournir des sorties par n'importe quelle méthode standard , tout en prenant note que ces failles sont interdites par défaut. Il s'agit de code-golf, donc la soumission la plus courte (notée en octets) gagne!

Cas de test

A, B -> p (indexé 0) / p (indexé 1)

1234, 32 -> 1/2
3456, 3 -> 4/5
378, 1824 -> 0/1
1824, 378 -> 4/5
67, 267 -> Tout ou partie parmi: [1, 2] / [2, 3]
435, 1 -> Tout ou partie parmi: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Tout ou partie parmi: [5, 6] / [6, 7]

Pour plus de commodité, voici une liste de tuples représentant chaque paire d'entrées:

[(1234, 32), (3456, 3), (378, 1824), (1824, 378), (67, 267), (435, 1), (378100, 1878980901)]

code-golf number-theory primes integer M. Xcoder
la source

1

J'ai l'impression que c'est biaisé vers 05AB1E ...

caird coinheringaahing

1

Pouvons-nous sortir le nombre résultant qui a minimisé les facteurs premiers au lieu de l'indice de l'insertion? par exemple dans votre premier cas de test 132234au lieu de 1.

dylnan

2

@dylnan Je vais dire non cette fois.

M. Xcoder

8

Husk , 16 octets

§◄öLpr§·++⁰↑↓oΘŀ

Attend les entrées sous forme de chaînes, essayez-les en ligne!

Explication

§◄(öLpr§·++⁰↑↓)(Θŀ)  -- input A implicit, B as ⁰ (example "1234" and "32")
§ (           )(  )  -- apply A to the two functions and ..
  (ö          )      --   | "suppose we have an argument N" (eg. 2)
  (    §      )      --   | fork A and ..
  (         ↑ )      --     | take N: "12"
  (          ↓)      --     | drop N: "34"
  (     ·++⁰  )      --   | .. join the result by B: "123234"
  (   r       )      --   | read: 123234
  (  p        )      --   | prime factors: [2,3,19,23,47]
  ( L         )      --   | length: 5
  (öLpr§·++⁰↑↓)      --   : function taking N and returning number of factors
                            in the constructed number
               ( ŀ)  --   | range [1..length A]
               (Θ )  --   | prepend 0
               (Θŀ)  --   : [0,1,2,3,4]
 ◄                   -- .. using the generated function find the min over range

ბიმო
la source

7

MATL , 25 octets

sh"2GX@q:&)1GwhhUYfn]v&X<

Les entrées sont des chaînes dans l'ordre inverse. La sortie est basée sur 1. S'il y a égalité, la position la plus basse est sortie.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

s         % Implicitly input B as a string. Sum (of code points). Gives a number
h         % Implicitly input A as a string. Concatenate. Gives a string of length
          % N+1, where N is the length of A
"         % For each (that is, do N+1 times)
  2G      %   Push second input
  X@      %   Push 1-based iteration index
  q       %   Subtract 1
  :       %   Range from 1 to that. Gives [] in the first iteration, [1] in
          %   the second, ..., [1 2 ... N] in the last
  &)      %   Two-output indexing. Gives a substring with the selected elements,
          %   and then a substring with the remaining elements
  1G      %   Push first input
  whh     %   Swap and concatenate twice. This builds the string with B inserted
          %   in A at position given by the iteration index minus 1
  U       %   Convert to string
  Yf      %   Prime factors
  n       %   Number of elements
]         % End
v         % Concatenate stack vertically
&X<       % 1-based index of minimum. Implicitly display

Luis Mendo
la source

6

Pyth, 20 13 11 octets

.mlPsXbQzhl

Essayez-le en ligne

Explication

.mlPsXbQzhl
.m    b         Find the minimum value...
         hl     ... over the indices [0, ..., len(first input)]...
  lP            ... of the number of prime factors...
    sX Qz       ... of the second input inserted into the first.

la source

3

Gelée , 21 octets

D©L‘Ṭœṗ¥€®żF¥€VÆfL€NM

Essayez-le en ligne!

-1 merci à M. Xcoder .

Renvoie toutes les positions possibles.

Erik le Outgolfer
la source

3

Japt , 22 21 octets

Cela m'a paru beaucoup trop long pendant que je l'écrivais mais, en regardant certaines des autres solutions, cela semble en fait quelque peu compétitif. Pourtant, il y a probablement un peu de place à l'amélioration - Cela cNq)me dérange en particulier. Explication à suivre.

Prend la première entrée sous forme de chaîne et la seconde sous forme d'entier ou de chaîne. Le résultat est indexé 0 et renverra le premier index s'il existe plusieurs solutions.

ÊÆiYVÃcNq)®°k Ê
b@e¨X

Essayez-le

Explication

      :Implicit input of string U and integer V.
Ê     :Get the length of U.
Æ     :Generate an array of the range [0,length) and map over each element returning ...
iYV   :  U with V inserted at index Y.
Ã     :End mapping
c     :Append ...
Nq    :  The array of inputs joined to a string.
®     :Map over the array.
°     :Postfix increment - casts the current element to an integer.
k     :Get the prime divisors.
Ê     :Get the length.
\n    :The newline allows the array above to be assigned to variable U.
b     :Get the first index in U that returns true ...
@     :  when passed through a function that ...
e     :    checks that every element in U...
¨     :    is greater than or equal to...
X     :    the current element.
      : Implicit output of resulting integer.

Hirsute
la source

2

PowerShell , 228 octets

param($a,$b)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$p=@{};,"$b$a"+(0..($x=$a.length-2)|%{-join($a[0..$_++]+$b+$a[$_..($x+1)])})+"$a$b"|%{$p[$i++]=(f $_).count};($p.GetEnumerator()|sort value)[0].Name

Essayez-le en ligne!

(Semble long / suggestions de golf bienvenues. Expire également sur TIO pour le dernier cas de test, mais l'algorithme devrait fonctionner pour ce cas sans problème.)

PowerShell n'a pas de facteurs de factorisation principaux intégrés, donc cela emprunte du code à ma réponse sur Prime Factors Buddies . C'est la functiondéclaration de la première ligne .

Nous prenons la saisie $a,$bet définissons ensuite $pune table de hachage vide. Ensuite, nous prenons la chaîne $b$a, la transformons en un tableau singleton avec l'opérateur virgule ,et nous concaténons le tableau avec des éléments . Le truc est une boucle $a, insérée $bà chaque point, enfin concaténée avec le tableau $a$b.

À ce stade, nous avons un tableau d' $binséré à chaque point $a. Nous envoyons ensuite ce tableau via une boucle for |%{...}. Chaque itération, nous insérons dans notre Hashtable à la position $i++du .countcombien de facteurs principaux de fcet élément particulier $_a.

Enfin, nous sortla table de hachage basée sur values, prenons la 0th de celui-ci, et sélectionnez son Name(c'est-à-dire le $ide l'index). Cela reste sur le pipeline et la sortie est implicite.

AdmBorkBork
la source

2

05AB1E , 18 octets

gƒ¹õ«N¹g‚£IýÒg})Wk

Essayez-le en ligne!

Emigna
la source

2

05AB1E , 27 21 octets

ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk

Essayez-le en ligne!

Il renvoie le p le moins indexé .

Merci à @Enigma pour -6 octets!

Explication

ηõ¸ì                  # Push the prefixes of A with a leading empty string -- [, 1, 12, 123, 1234]
    ¹.sRõ¸«)          # Push the suffixes of A with a tailing empty space. -- [1234, 123, 12, 1, ]
            ø         # Zip the prefixes and suffixes
             ε    }   # Map each pair with...
              IýÒg    # Push B, join prefix - B - suffix, map with number of primes
                   Wk # Push the index of the minimum p

Kaldo
la source

1

En utilisant la même méthode, vous pouvez économiser 6 octets en réécrivant ceci sous ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk.

Emigna

1

Nettoyer , 165 ... 154 octets

import StdEnv,StdLib
@n h#d=hd[i\\i<-[2..h]|h rem i<1]
|d<h= @(n+1)(h/d)=n
?a b=snd(hd(sort[(@0(toInt(a%(0,i-1)+++b+++a%(i,size a))),i)\\i<-[0..size a]]))

Essayez-le en ligne!

Οurous
la source

1

Python 2 , 165 146 bytes

Dix-neuf octets enregistrés grâce à Erik l'Outgolfer .

O=lambda n:n>1and-~O(n/min(d for d in range(2,n+1)if n%d<1))
def f(A,B):L=[int(A[:j]+B+A[j:])for j in range(len(A)+1)];print L.index(min(L,key=O))

Essayez-le en ligne!

Jonathan Frech
la source

146 octets

Erik the Outgolfer

@EriktheOutgolfer Merci.

Jonathan Frech

0

JavaScript (ES6), 120 octets

Prend l'entrée en 2 chaînes. Renvoie une position indexée 0.

f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

Cas de test

Afficher l'extrait de code

f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

console.log(f('1234','32'))   // 1
console.log(f('3456','3'))    // 4
console.log(f('378','1824'))  // 0
console.log(f('1824','378'))  // 4
console.log(f('67','267'))    // 1
console.log(f('435','1'))     // 1

Développer l'extrait

Arnauld
la source

0

J, 60 octets

4 :'(i.<./)#@q:>".@(,(":y)&,)&.>/"1({.;}.)&(":x)"0 i.>:#":x'

Dyade explicite. Prend B à droite, A à gauche.

Sortie indexée 0.

Il pourrait être possible de s'améliorer en n'utilisant pas de boîtes.

Explication:

  4 :'(i.<./)#@q:>".@(,(":x)&,)&.>/"1({.;}.)&(":y)"0 i.>:#":y'  | Whole program
  4 :'                                                       '  | Define an explicit dyad
                                                     i.>:#":y   | Integers from 0 to length of y
                                                  "0            | To each element
                                     ({.;}.)&(":y)              | Split y at the given index (result is boxed)
                     (,(":x)&,)&.>/"1                           | Put x inbetween, as a string
                  ".@                                           | Evaluate
                 >                                              | Unbox, makes list
             #@q:                                               | Number of prime factors of each
      (i.>./)                                                   | Index of the minimum

Bolce Bussiere
la source

0

Python 3, 128 octets

Indexé 0; prend les chaînes comme paramètres. -6 octets grâce à Jonathan Frech.

from sympy.ntheory import*
def f(n,m):a=[sum(factorint(int(n[:i]+m+n[i:])).values())for i in range(len(n)+1)];return a.index(min(a))

0WJYxW9FMN
la source

:\n a-> :a.

Jonathan Frech

0

Python, 122 octets

f=lambda n,i=2:n>1and(n%i and f(n,i+1)or 1+f(n/i,i))
g=lambda A,B:min(range(len(A)+1),key=lambda p:f(int(A[:p]+B+A[p:])))

En pratique, cela dépasse assez rapidement la profondeur de récursivité maximale par défaut.

user84207
la source

Minimisez le nombre de facteurs premiers grâce à l'insertion

Spécifications

Cas de test

Réponses:

Husk , 16 octets

Explication

MATL , 25 octets

Explication

Pyth, 20 13 11 octets

Explication

Gelée , 21 octets

Japt , 22 21 octets

Explication

PowerShell , 228 octets

05AB1E , 18 octets

05AB1E , 27 21 octets

Explication

Nettoyer , 165 ... 154 octets

Python 2 , 165 146 bytes

JavaScript (ES6), 120 octets

Cas de test

J, 60 octets

Explication:

Python 3, 128 octets