Даны целые положительные числа A и B , возвращает позицию р , что сводит к минимуму число простых факторов ( с учетом кратности) в результате целого числа, когда B будет вставлен в А на р .

Например, учитывая A = 1234 и B = 32 , это возможные вставки (с p -индексированным 0) и соответствующая информация об их простых множителях:

р | Результат | Основные факторы | Ω (N) / количество

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

Вы можете видеть, что результат имеет минимальное число простых факторов, 3, когда p равно 1. Поэтому в данном конкретном случае вы должны вывести 1 .

Спекуляции

Если есть несколько позиций p, которые минимизируют результат, вы можете выбрать вывод всех или любой из них.
Вы можете выбрать 0-индексирование или 1-индексирование для p , но этот выбор должен быть последовательным.
A и B могут быть приняты как целые числа, строки или списки цифр.
Вы можете соревноваться на любом языке программирования и можете принимать и выводить данные любым стандартным методом , при этом отмечая, что эти лазейки по умолчанию запрещены. Это код-гольф, поэтому выигрывает самое короткое представление (в байтах)!

Контрольные примеры

A, B -> p (0-индексированный) / p (1-indexed)

1234, 32 -> 1/2
3456, 3 -> 4/5
378, 1824 -> 0/1
1824, 378 -> 4/5
67, 267 -> Любой или все среди: [1, 2] / [2, 3]
435, 1 -> Любой или все среди: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Любой или все среди: [5, 6] / [6, 7]

Для удобства вот список кортежей, представляющих каждую пару входов:

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

code-golf number-theory primes integer Мистер Xcoder
источник

1

У меня такое ощущение, что это смещено в сторону 05AB1E ...

Caird Coneheringaahing

1

Можем ли мы вывести результирующее число с минимизированными простыми множителями вместо индекса вставки? например, в вашем первом тестовом примере 132234вместо 1.

Дилнан

2

@dylnan Я собираюсь сказать нет на этот раз.

г-н Xcoder

8

Шелуха , 16 байт

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

Ожидается ввод в виде строк, попробуйте онлайн!

объяснение

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

ბიმო
источник

7

MATL , 25 байт

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

Входные данные представляют собой строки в обратном порядке. Выход основан на 1. Если есть ничья, выводится самая низкая позиция.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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

Луис Мендо
источник

6

Pyth, 20 13 11 байт

.mlPsXbQzhl

Попробуйте онлайн

объяснение

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

источник

3

Желе , 21 байт

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

Попробуйте онлайн!

-1 спасибо мистеру Xcoder .

Возвращает все возможные позиции.

Эрик Outgolfer
источник

3

Japt , 22 21 байт

Это чувствовалось слишком долго, пока я писал это, но, глядя на некоторые другие решения, это на самом деле кажется несколько конкурентным. Тем не менее, вероятно, есть немного возможностей для совершенствования - cNq)в частности, меня это раздражает. Объяснение, чтобы следовать.

Принимает первый ввод как строку, а второй как целое число или строку. Результат имеет индекс 0 и вернет первый индекс, если существует несколько решений.

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

Попытайся

объяснение

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

мохнатый
источник

2

PowerShell , 228 байт

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

Попробуйте онлайн!

(Кажется, что длинные предложения по игре в гольф приветствуются. Также время ожидания TIO для последнего тестового случая истекло, но алгоритм должен работать для этого случая без проблем.)

PowerShell не имеет встроенных основных факторов факторизации, поэтому этот код заимствован из моего ответа на Prime Factors Buddies . Это объявление первой строки function.

Мы берем входные данные $a,$bи затем устанавливаем $pпустую хеш-таблицу. Далее мы берем строку $b$a, превращаем ее в одноэлементный массив с помощью оператора запятой ,и объединяем массив с помощью вещи . Материал представляет собой через петлю $a, вставив $bв любой точке, в конце концов массива сцепляются с $a$b.

На данный момент у нас есть массив $bвставленных в каждой точке $a. Затем мы отправляем этот массив через цикл for |%{...}. Каждая итерация, мы вводим в нашу хэш - таблицу в позиции сколько простых делителей , что конкретный элемент имеет.$i++.countf$_

Наконец, мы sortиспользуем хеш-таблицу на основе values, берем 0ее и выбираем ее Name(т. $iЕ. Индекс). Это осталось на конвейере и вывод неявный.

AdmBorkBork
источник

2

05AB1E , 18 байт

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

Попробуйте онлайн!

Emigna
источник

2

05AB1E , 27 21 байт

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

Попробуйте онлайн!

Возвращает самый низкий 0-индексированный р .

Спасибо @Enigma за -6 байт!

объяснение

ηõ¸ì                  # 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
источник

1

Используя тот же метод, вы можете сохранить 6 байтов, переписав это как ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk.

Эминья

1

Чисто , 165 ... 154 байта

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

Попробуйте онлайн!

Οurous
источник

1

Python 2 , 165 146 байт

Сохранено девятнадцать байтов благодаря Эрику Аутгольферу .

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

Попробуйте онлайн!

Джонатан Фрех
источник

146 байт

Эрик Outgolfer

@EriktheOutgolfer Спасибо.

Джонатан Фрех

0

JavaScript (ES6), 120 байт

Принимает ввод как 2 строки. Возвращает позицию с 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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Arnauld
источник

0

J, 60 байт

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

Явная диада. Принимает B справа, A слева.

0-индексированный вывод.

Может быть возможно улучшить, не используя коробки.

Объяснение:

  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
источник

0

Python 3, 128 байт

0 индексированные; принимает в качестве параметров строки -6 байт благодаря Джонатану Фреху.

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
источник

:\n a-> :a.

Джонатан Фрех

0

Python, 122 байта

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

На практике это превышает максимальную глубину рекурсии по умолчанию довольно быстро.

user84207
источник

Минимизируйте количество основных факторов путем вставки

Спекуляции

Контрольные примеры

Ответы:

Шелуха , 16 байт

объяснение

MATL , 25 байт

объяснение

Pyth, 20 13 11 байт

объяснение

Желе , 21 байт

Japt , 22 21 байт

объяснение

PowerShell , 228 байт

05AB1E , 18 байт

05AB1E , 27 21 байт

объяснение

Чисто , 165 ... 154 байта

Python 2 , 165 146 байт

JavaScript (ES6), 120 байт

Контрольные примеры

J, 60 байт

Объяснение:

Python 3, 128 байт