Факторизация массива

13

Учитывая массив положительных целых чисел, выведите стабильный массив различных простых множителей этих чисел. Другими словами, для каждого целого числа во входных данных по порядку, получайте его простые множители, сортируйте их и добавляйте к выходным данным все простые числа, которых еще нет в выходных данных.

Тестовые случаи

[1,2,3,4,5,6,7,8,9,10] -> [2,3,5,7]
[10,9,8,7,6,5,4,3,2,1] -> [2,5,3,7]
[100,99,98,1,2,3,4,5] -> [2,5,3,11,7]
[541,60,19,17,22] -> [541,2,3,5,19,17,11]
[1,1,2,3,5,8,13,21,34,45] -> [2,3,5,13,7,17]
[6,7,6,7,6,7,6,5] -> [2,3,7,5]
[1] -> []
[8] -> [2]
[] -> []

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

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.

code-golf array-manipulation primes Стивен
источник
Песочница
Стивен
5
Это одна из тех проблем, которые я считаю «слишком простыми». Почти каждый ответ будет выглядеть следующим образом: (а) цикл ввода и код факторизации Е. Олде с условным добавлением; (б) цепочка из четырех встроенных элементов. Там просто не так много места для творчества. Может быть, ответы докажут, что я не прав, но я сомневаюсь в этом. В гольфе есть немного больше, чем просто факторизация, и это было сделано до смерти.
Линн
1
@ Линн это тривиально для игры в гольф, но нетривиально почти для всего остального. Не уверен, что это основание для тривиальности здесь: /
Стивен
Можете ли вы сказать мне, что является "отличными основными факторами" 1?
J42161217
1
@DigitalTrauma Да. В противном случае это будет просто «вывести множество всех простых факторов ввода»
Стивен

Ответы:

5

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

1 байт сохранен благодаря @Zgarb .

uṁp

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

объяснение

UUP Полная программа.

  p Основные факторы каждого.
 ṁ Карта функции над списком и объединить результат.
ты уникален.
Мистер Xcoder
источник
3
Σ†может быть ṁ.
Згарб
@ Zgarb Большое спасибо. Как вы можете сказать, это мой первый ответ на Husk :)
Mr. Xcoder
Приятно видеть новых людей, использующих шелуху. :)
Згарб
1
@ Zgarb Кажется, это очень приятно (особенно когда это превосходит Jelly: P)
г-н Xcoder
5

Утилиты Bash + GNU, 37

  • 21 байт сохранен благодаря @muru (вау!)
factor|tr \  \\n|awk '!/:/&&!a[$0]++'

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

Цифровая травма
источник
1
Я думаю, что это nl|sort|...можно сделать с помощью awk: awk '!a[$0]++'(распечатать, если не видел раньше; поэтому порядок никогда не теряется), сохраняя 15 байтов. Затем sedкоманду можно удалить, используя чуть более длинную awk: factor|awk '!/:/&&!a[$0]++' RS='[ \n]+'(разделить записи по пробелам и символам новой строки, пропустить записи с помощью :), сохранив еще 4 байта.
Муру
1
Я только что понял, что могу сохранить еще два байта в предыдущем комментарии, используя tr: factor|tr \ \\n|awk '!/:/&&!a[$0]++'(это два пробела после первой обратной косой черты)
muru
@muru потрясающе - спасибо! (Я бы не расстроился, если бы вы опубликовали это как свой собственный ответ, который значительно превзошел мой оригинал)
Digital Trauma
4

MATL , 6 байтов

"@Yfvu

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

Объяснение:

"      % Loop over input
 @     % Push the array element
  Yf   % Prime factors
    v  % Concatenate entire stack vertically (does nothing the first iteration)
     u % Stably get distinct (unique, in MATLAB terminology) elements. Does so every loop but this is code golf, not fastest code.

Интересные трюки MATL: как правило, все функции применяются к векторам (массивам) так же легко. Но в этом случае число факторов является переменным для каждого входа, и Matlab и, соответственно, MATL имеют дело только с квадратными матрицами, поэтому мне пришлось использовать цикл for ".

Кроме того, MATL имеет две основные операторы конкатенации: hи v, по горизонтали и вертикали конкатенацию. Их поведение существенно отличается: vобъединяет весь стек, даже если он имеет только один элемент, как в нашей первой итерации. hзанимает ровно два элемента и потерпит неудачу, если присутствует только один, что делает его непригодным для данного приложения.

Sanchises
источник
4

Brachylog , 6 байт

ḋᵐ↔ᵐcd

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

Брахилог , 6 байт

ḋᵐoᵐcd

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

объяснение

ḋᵐ Карта с простой разложением (которая возвращает факторы в обратном порядке).
  Each поменять местами каждый (или oᵐ - заказать каждый).
    c сцепить (сплющить).
     д Дублировать.
Мистер Xcoder
источник
3

PowerShell , 102 байта

param($x)$a=@();$x|%{$a+=(2..($z=$_)|?{!($z%$_)-and'1'*$_-match'^(?!(..+)\1+$)..'}|sort)};$a|select -u

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

(Идея факторизации заимствована из ответа Тесселлатинга Геклера на: «Отстань от меня, Сатана-Прайм!»)

Принимает ввод как буквенный массив $x. Создает новый пустой массив $a. Перебирает $x. Каждую итерацию мы перебираем 2до текущего числа, проверяем, является ли этот фактор -andпростым, затем |sortвыводим его и добавляем к нему $a. Когда мы закончим $x, мы выводим, $aно |selectтолько их -uуникальные номера. Это использует тот факт, что uniqueify идет слева направо, сохраняя первое вхождение, которое соответствует описанию проблемы. Эти числа остаются в конвейере и вывод неявный.

— AdmBorkBork
источник
3

CJam, 11 байт

{:mfe__&1-}

Функция, которая принимает массив целых и выдает массив целых.

Тестовая версия

— geokavel
источник
Как бы я дифференцировал вывод с несколькими символами? По крайней мере, для моего (онлайн) тестирования он выводит строку, а не массив целых чисел.
— Стивен
Как функция, выходной тип данных представляет собой массив целых чисел. CJam автоматически печатает этот стек и печатает массивы без разделителей. Я не знаю, достаточно ли это подходит для ваших целей. Если вы хотите, чтобы разделители были добавлены S*в закрывающую скобку.
— геокавель
Я считаю, что основанные на стеке langs могут в любом случае выводить с помощью ToS, так что все в порядке, мне просто интересно. Благодарю.
— Стивен
2

Mathematica, 64 байта

Select[DeleteDuplicates[First/@FactorInteger@#~Flatten~1],#>1&]&

вход

[{100, 99, 98, 1, 2, 3, 4, 5}]

J42161217
источник
Select[#&@@@Gather[#&@@@Join@@FactorInteger@#],#>1&]&
matrix89
2

Haskell, 77 байт

import Data.List
x!y|y>x=[]|x`mod`y<1=y:(x`div`y)!y|1<2=x!(y+1)
nub.((!2)=<<)

Объяснение:

  • x!yоператор возвращает список всех главных факторовx , которые больше или равноy
  • (!2)функция возвращает список всех простых делителей аргумента
  • функция в последней строке реализует необходимую функциональность

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

Кристиан Лупаску
источник
2

Брахилог , 6 байт

ḋᵐoᵐcd

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

объяснение

ḋᵐ         Map prime decomposition
  oᵐ       Map order
    c      Concatenate
     d     Remove duplicates
Fatalize
источник
Фейс для [10,9,8,7,6,5,4,3,2,1]. Должно быть [2, 5, 3, 7], нет[2, 3, 5, 7]
г-н Xcoder
Вы можете исправить это за +1 байт: ḋᵐoᵐcd
Мистер Кскодер
@ Mr.Xcoder Спасибо, исправлено. Впрочем, довольно бессмысленное требование.
Роковая
Это на самом деле не бессмысленно, так как это крошечное, чуть менее тривиальное. Я также опубликовал свой собственный ответ, но вместо порядка я сначала использовал обратный. Не уверен, почему основные факторы генерируются в обратном порядке?
Мистер Кскодер
@ Фатализировать хорошо - задача не в том, чтобы «отсортировать отдельные простые факторы списка», а в том, чтобы «перебрать список и добавить различные простые факторы».
Стивен
2

Ом v2 , 3 байта

Еще один 3-х байтовый (благодаря языкам с авто-векторизацией).

m{U

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

объяснение

Основные факторы. Авто-векторизация по входу.
 {Свести.
  U Uniquify.
Мистер Xcoder
источник
2

Japt , 6 байт

mk c â

Проверь это

объяснение

Неявный ввод массива U. Map ( m) над ним, получая факторы ( k) каждого элемента. Flatten ( c), получить уникальные элементы ( â) и неявно выводить.

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

Python 3 , 128 125 116 байтов

Это чистое решение Python. Нет пакетов. Спасибо Halvard за сохранение 9 байтов.

def f(l):y=[k for i in l for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))];print(sorted({*y},key=y.index))

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

Python 2 , 133, 127, 126 байт

def f(l):y=sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]);print sorted(set(y),key=y.index)

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

Python 2 , 142 138 134 байта

l=input();r=[]
for i in sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]):r+=[i]*(i not in r)
print r

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

Очень удивлен, что пока не было ответа от Python. Работаю в гольф.

Мистер Xcoder
источник
116 байтов Python 3
Halvard Hummel
@HalvardHummel Спасибо
мистер Xcoder
2

Deorst , 16 байт

EDkE]l1FeFPkEQE_

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

Сделано с помощью @cairdcoinheringaahing в чате Deorst (обратите внимание, что решения разные).

объяснение

EDkE] l1FeFPkEQE_ Полная программа.

ED Нажмите список делителей каждого элемента.
  k Не допускать переупорядочения стека.
   E] Свести стек.
     l1Fe Удалить 1s из стека (потому что caird бросился и сделал 1 штрих!) - должен быть удален в будущих языковых выпусках.
         Ф. П. Держите простые числа.
           k Не допускать переупорядочения стека.
            EQ Дедупликация.
              E_ Вывести результат.
Мистер Xcoder
источник
2

Deorst , 16 байт

EDkE]EQFPkl1FeE_

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

Сделано с помощью @ Mr.Xcoder. Это слишком долго для языка псевдогольфинга.

Как это устроено

EDkE]EQFPkl1FeE_ - Full program, implicit input: [1,2,3,4,5]

ED               - Get divisors. Vectorizes. STACK = [[1], [1,2], [1,3], [1,2,4], [1,5]]
  k              - Turn off sorting for the next command
   E]            - Flatten the stack. STACK = [1, 1, 2, 1, 3, 1, 2, 4, 1, 5]
     EQ          - Deduplicate stack in place. STACK = [1, 2, 3, 4, 5]
       FP        - Filter by primality 1 is considered prime. STACK = [1, 2, 3, 5]
         k       - Turn off sorting for the next command
          l1     - Push 1. STACK = [1, 2, 3, 5, 1]
            Fe   - Filter elements that are equal to the last element. STACK = [2, 3, 5]
              E_ - Output the whole stack
Кэрд
источник
1

Пайк , 4 байта

mPs}

Попробуй это здесь!

mP   -   map(factorise, input)
  s  -  sum(^)
   } - uniquify(^)
синий
источник
Ой, я вас ниндзя плохо - Хорошо, у нас разные подходы :)
Мистер Xcoder
: P Разница в один байт. Я думаю, что это разрешено, хотя или по крайней мере в соответствии с последним консенсусом, который я прочитал
Blue
Да, разрешены повторяющиеся ответы, даже
побайтные
1

МОЙ, 17 байт

⎕Ḋḟ’⊢f(‘53ǵ'ƒf(ū←

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

Как?

  • ⎕ оцененный вклад
  • Ḋ делители (векторизация / вектизация)
  • ḟ расплющить
  • ’⊢f(‘декремент, фильтр, приращение (удаляет 1)
  • 53ǵ'строка 'P'в кодовой странице MY, которая проверяет первичность. К сожалению, 0x35=53это 16-е простое число, и нет команды для добавления 16в стек> _ <.
  • ƒ как функция
  • f( фильтр по этому
  • ū uniquify
  • ← выход
Zachary
источник
1

C ++, 118 байт

[](auto n){decltype(n)r;for(int m:n)for(int i=1,j;i++<m;){j=m%i;for(int x:r)j|=!(i%x);if(!j)r.push_back(i);}return r;}

Необходимо передать вход в a std::vector<int>, возвращает другой std::vector<int>для вывода.

HVD
источник
1

J, 10 байт

~.(#~*),q:

Я уверен, что какой-нибудь умный Джер сможет сделать это короче.

Грегори Хигли
источник
1

Python 2, 88 119 103 байта

Вот так. С правильной сортировкой.

def f(l,s=[]):[s.append(x) for x in sum([list(primefac(i)) for i in l],[]) if x not in s];print s
from primefac import*

По-видимому, я не могу заставить его работать на TIO, потому что пакет не поддерживается. Это работает на моей машине, хотя. Вот мои тестовые результаты:

f([1,2,3,4,5,6,7,8,9,10],[])     #[2, 3, 5, 7]
f([10,9,8,7,6,5,4,3,2,1],[])     #[2, 5, 3, 7]
f([100,99,98,1,2,3,4,5],[])      #[2, 5, 3, 11, 7]
f([541,60,19,17,22],[])          #[541, 2, 3, 5, 19, 17, 11]
f([1,1,2,3,5,8,13,21,34,45],[])  #[2, 3, 5, 13, 7, 17]
f([6,7,6,7,6,7,6,5],[])          #[2, 3, 7, 5]
f([1],[])                        #[]
f([8],[])                        #[2]
f([],[])                         #[]

Как-то я не смог сделать функцию лямбда-функцией. Всякий раз, когда я пытаюсь вернуть понимание списка, он возвращает [Нет, Нет, ...]. Если я просто что-то упускаю, кто-то может указать на эту ошибку? Спасибо за ответ!

Редактировать:

Используя алгоритм сортировки Mr. Xcoders, я мог сократить код на 16 байт. Спасибо за эту часть.

from primefac import*
def f(l):a=sum([list(primefac(i))for i in l],[]);print sorted(set(a),key=a.index)
Саймон
источник
Это не кажется правильным. Второй контрольный пример должен вывести [2, 5, 3, 7]. Порядок выходных данных имеет значение.
Mego
sorted(set().union(*map(primefac,l)))
Алекс Холл
Порядок выходных данных важен. Перечитайте объяснение или посмотрите на другие ответы - я не знаю, как еще это объяснить.
Стивен
@Стивен. Обновленная процедура с правильным выводом. Мне потребовалось некоторое время, пока я не заметил различия в каждой строке. Фокус при чтении очень помогает.
Симон
@ Симон сэкономит три байта, избавившись от пробелов после скобок - s.append(x) for-> s.append(x)for, primefac(i)) for-> primefac(i))for, []) if->[])if
Стивен
1

Braingolf , 7 байтов

&(p)u=;

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

О, смотри, это в основном цепочка из 4 встроенных

объяснение

&(p)u=;  Implicit input from commandline args
 (.)     Sandbox loop, sandboxes each item in a separate stack and runs the
         code within the loop.
&        Append the entire sandboxed stack when loop ends, rather than only the
         top of stack after each iteration
  p      Prime factors
    u    Unique
     =   Print stack
      ;  Suppress implicit output
Skidsdev
источник
Терпит неудачу за [10,9,8,7,6,5,4,3,2,1]. - Порядок имеет значение: вы должны вернуться[2, 5, 3, 7] вместо [2, 3, 5, 7].
Мистер Кскодер
Вы можете исправить это за -1 байт, хотя . Так как здесь Kтолько вред.
г-н Xcoder
@ Mr.Xcoder, да, да, я не понял, что они должны быть в порядке появления, а не в порядке возрастания. Исправлено
Skidsdev