Biorąc pod uwagę dwie dodatnie liczby całkowite A i B , zwróć pozycję p, która minimalizuje liczbę czynników pierwszych (licząc krotność) wynikowej liczby całkowitej, gdy B zostanie wstawione do A w punkcie p .

Na przykład, biorąc pod uwagę A = 1234 i B = 32 , są to możliwe wstawienia (przy czym p ma indeks 0) i odpowiednie informacje o ich czynnikach głównych:

p | Wynik | Czynniki pierwsze | Ω (N) / Count

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

Widać, że wynik ma minimalną liczbę czynników pierwszych, 3, gdy p wynosi 1. W tym konkretnym przypadku powinieneś otrzymać 1 .

Okular

• Jeśli istnieje wiele pozycji p, które minimalizują wynik, możesz wybrać wyjście wszystkich z nich lub dowolnej z nich.

• Możesz wybrać indeksowanie 0 lub indeksowanie 1 dla p , ale ten wybór musi być spójny.

• A i B mogą być traktowane jako liczby całkowite, ciągi znaków lub listy cyfr.

• Możesz konkurować w dowolnym języku programowania i możesz przyjmować dane wejściowe i generować dane wyjściowe za pomocą dowolnej standardowej metody , zwracając uwagę, że te luki są domyślnie zabronione. To jest golf golfowy, więc wygrywa najkrótsze zgłoszenie (w bajtach)!

Przypadki testowe

A, B -> p (indeksowane 0) / p (indeksowane 1)

1234, 32 -> 1/2
3456, 3 -> 4/5
378,1824 -> 0/1
1824, 378 -> 4/5
67, 267 -> Dowolne lub wszystkie spośród: [1, 2] / [2, 3]
435, 1 -> Dowolne lub wszystkie spośród: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Dowolne lub wszystkie spośród: [5, 6] / [6, 7]

Dla wygody oto lista krotek reprezentujących każdą parę danych wejściowych:

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

Łuska , 16 bajtów

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

Oczekuje wprowadzania jako ciągów, spróbuj online!

Wyjaśnienie

§◄(ö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

MATL , 25 bajtów

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

Dane wejściowe są łańcuchami w odwrotnej kolejności. Wyjście jest oparte na 1. W przypadku remisu generowana jest najniższa pozycja.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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

Pyth, 20 13 11 bajtów

.mlPsXbQzhl

Wypróbuj online

Wyjaśnienie

.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.

Galaretka , 21 bajtów

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

Wypróbuj online!

-1 dzięki Mr. Xcoder .

Zwraca wszystkie możliwe pozycje.

Japt , 22 21 bajtów

Wydawało mi się, że jest to zbyt długo, kiedy to pisałem, ale patrząc na niektóre inne rozwiązania, wydaje się to nieco konkurencyjne. Mimo to prawdopodobnie jest trochę miejsca na ulepszenia - cNq)w szczególności mnie to denerwuje. Wyjaśnienie do naśladowania.

Pobiera pierwsze wejście jako ciąg znaków, a drugie jako liczbę całkowitą lub ciąg znaków. Wynik jest indeksowany na 0 i zwróci pierwszy indeks, jeśli istnieje wiele rozwiązań.

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

Spróbuj

Wyjaśnienie

      :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.

PowerShell , 228 bajtów

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

Wypróbuj online!

(Wydaje się, że długie / golfowe sugestie są mile widziane. Również limit czasu dla TIO dla ostatniego przypadku testowego, ale algorytm powinien działać dla tego przypadku bez problemu.)

Program PowerShell nie ma żadnych wbudowanych głównych faktoryzacji, więc pożycza kod z mojej odpowiedzi na temat znajomych Prime Factors . To functiondeklaracja pierwszego wiersza .

Bierzemy dane wejściowe, $a,$ba następnie ustawiamy $psię jako pusta tablica mieszająca. Następnie bierzemy ciąg $b$a, zamieniamy go w tablicę singletonową za pomocą operatora przecinka ,i konkatenujemy tablicę za pomocą rzeczy . Materiał jest pętla poprzez $awstawienie $bw każdym punkcie, w końcu łączone z macierzach $a$b.

W tym momencie mamy tablicę $bwstawioną w każdym punkcie $a. Następnie wysyłamy tę tablicę przez pętlę for |%{...}. Każda iteracja, możemy wstawić do naszej hashtable w pozycji o ile czynniki pierwsze , że dany element ma.$i++.countf$_

Na koniec mamy sorttablicę mieszającą opartą na values, weźmy 0jej i wybierz jej Name(tj. $iIndeks). Pozostaje to w potoku, a dane wyjściowe są niejawne.

05AB1E , 18 bajtów

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

Wypróbuj online!

05AB1E , 27 21 bajtów

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

Wypróbuj online!

Zwraca najniższą p -indeksowaną przez 0 .

Dzięki @Enigma za -6 bajtów!

Wyjaśnienie

ηõ¸ì                  # 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

Czysty , 165 ... 154 bajtów

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]]))

Wypróbuj online!

Python 2 , 165 146 bajtów

• Zaoszczędzono dziewiętnaście bajtów dzięki Erikowi 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))

Wypróbuj online!

JavaScript (ES6), 120 bajtów

Pobiera dane wejściowe jako 2 ciągi. Zwraca pozycję z indeksowaniem 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

Przypadki testowe

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

J, 60 bajtów

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

Wyraźna diada. Bierze B po prawej, A po lewej.

Wyjście indeksowane 0.

Może być możliwe ulepszenie poprzez nieużywanie skrzynek.

Wyjaśnienie:

  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

Python 3, 128 bajtów

0-indeksowane; przyjmuje parametry jako parametry. -6 bajtów dzięki Jonathanowi Frechowi.

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))

Python, 122 bajty

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:])))

W praktyce dość szybko przekracza domyślną maksymalną głębokość rekurencji.