2013 год имеет первостепенную факторизацию 3*11*61
. 2014 год имеет первостепенную факторизацию 2*19*53
. Интересное свойство относительно этих факторизаций является то , что существует различные простые числа в факторизациях 2013 и 2014 , что сумма к тому же номеру: 11+61=19+53=72
.
Напишите программу или функцию, которая принимает в качестве входных данных два натуральных числа больше 1 и возвращает истинное значение, если существует сумма выбранных простых множителей одного числа, равная сумме выбранных простых факторов во втором числе, и ложное значение в противном случае.
Разъяснения
- Можно использовать более двух основных факторов. Не все основные факторы числа должны быть использованы в сумме. Нет необходимости, чтобы число простых чисел, используемых из двух чисел, было одинаковым.
- Даже если простое число увеличивается до некоторой степени больше 1 при факторизации числа, его можно использовать только один раз в сумме простых чисел для числа.
- 1 не простое число.
- Оба входных номера будут меньше чем
2^32-1
.
Контрольные примеры
5,6
5=5
6=2*3
5=2+3
==>True
2013,2014
2013=3*11*61
2014=2*19*53
11+61=19+53
==>True
8,15
8=2^3
15=3*5
No possible sum
==>False
21,25
21=3*7
25=5^2
No possible sum (can't do 3+7=5+5 because of exponent)
==>False
Это код гольф. Стандартные правила применяются. Самый короткий код в байтах побеждает.
true
, поскольку они имеют общий фактор7
?Ответы:
Юлия,
9593 байтаОсновная функция
f
и она вызывает вспомогательную функциюg
.Ungolfed:
Сохранено 2 байта благодаря Дарту Алефале
источник
map(p->map
короче(m=map)(p->m
.Pyth, 11 байт
Ввод в форме
30,7
.источник
Pyth -
171211 байтСпасибо @FryAmTheEggman за исправление моего ответа и сохранение байта.
Тестовый пакет .
источник
ty
работает и сохраняет пока?Хаскелл,
115106 байтПример использования:
2013 # 2014
->True
.p
создает список всех основных факторов своего аргумента, удаляет дубликаты, создает список всех подпоследовательностей, удаляет первую (которая всегда является пустым списком) и, наконец, суммирует подпоследовательности.#
проверяет,p a
не равна ли разницаp a \\ p b
. Если не равны, у них есть хотя бы один общий элемент.источник
Japt, 25 байт
Выходы
true
илиfalse
. Попробуйте онлайн!Неуправляемый и объяснение
Для дополнительного байта вы можете разделить код factorize-unique-Объединить-Сумма между обоими входами с дополнительным преимуществом временной сложности
O(O(25-byte version)^2)
:источник
CJam, 23 байта
Проверьте это здесь.
Значение true будет объединять все общие суммы, значение false - пустая строка.
объяснение
источник
Брахилог ,
109 байтПопробуйте онлайн!
Предикат успешно возвращается,
[the sum, the sum]
если он существует, и не выполняется, если сумма не существует.-1 байт благодаря Fatalize (создателю Brachylog), напомнившему мне, что существует мета-предикат проверки .
источник
ᵛ - verify
вместо того,ˢ=
чтобы сохранить один байт.MATL , 23 байта
Использует текущий выпуск 2.0.2 , который является более ранним, чем этот вызов.
Номера представлены как два отдельных входа. Вывод
0
или1
.пример
объяснение
источник
Mathematica, 58 байт
Объяснение:
Это анонимная функция.
Сначала
IntersectingQ
проверяется, пересекаются ли два списка. Но входные данные являются числами, а не списками, поэтому он остается неоцененным. Например, если входными данными являются2013
и2014
, тогдаIntersectingQ@##&
возвращаетсяIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
это еще одна анонимная функция, которая принимает целое число, получает список ее простых факторов без повторений, получает набор мощности, удаляет пустой набор и затем получает сумму каждого набора. Так чтоTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
возвращается{3, 11, 61, 14, 64, 72, 75}
.Затем сопоставьте
Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
выражениеIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
иTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]
являются списками, поэтому мы можем получить результат сбора на этот раз.источник
IntersectingQ
первым - это здорово! :)PARI / GP , 98 байт
Factor, возьмите primes (
[,1]
), зациклите непустые подмножества, sum и uniq, затем пересекайте результат этого для двух чисел. Возвращаемое значение - это количество пересечений, которое является достоверным, если только они не равны 0.источник
APL (Dyalog Extended) ,
2317 байт SBCS-5 благодаря ngn
Анонимная негласная инфиксная функция.
Попробуйте онлайн!
⍥{
…}
Применить следующую анонимную функцию к обоим аргументам:⍭
главные факторы⍤
тогда∪
уникальные из тех,0+⍀.,
добавление таблицы уменьшения нуля, сцепленного с каждым фактором∊
ε NLIST (Flatten)∩
Перекресток⍤
тогда≢
подсчет тех1<
там больше одного? (один, потому что суммы без факторов)источник
p+.×⊤1↓⍳2*≢p←
->1↓∊(⊢,+)/0,⍨
1↓∊∘.+/0,¨
1↓∊0∘.+.,
продуктом inouter - как часто вы видите это :)⍥
правильно понимаю , это должно работать тоже:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
05AB1E ,
108 байт-2 байта благодаря @Emigna .
Попробуйте онлайн или проверьте все контрольные примеры .
Объяснение:
источник
f€æO`å¦à
должен работать на 8.Japt, 12 байт
Запустите его онлайн
источник
Python 3 , 206 байт
Это лямбда-функция (m), которая принимает 2 числа и возвращает набор, содержащий любые суммы простых факторов, которые у них общие. В Python это истинное значение, если оно не пустое, и значение Falsey, если оно пустое.
Изменить: Оказывается, мой первоначальный ответ не работал для простых входов, как указано @JoKing. Это было исправлено (наряду с некоторыми другими ошибками) при трагической стоимости в 40 байт.
Быстрое объяснение с использованием комментариев:
Попробуйте онлайн!
источник
5,6
, так как он не обрабатывает первичные входные данныеAPL (NARS), 50 символов, 100 байтов
здесь я нашел бы множество факторов на его аргумент;
была бы функция, которая находит все подмножества ... я должен сказать, что, кажется, {itsоператор itsArguments} ¨ (для каждого левого) и ¨ (для каждого правого) может имитировать цикл с фиксированным числом циклов, и ok в порядке в чтобы увидеть подмножества одного набора ... при таком взгляде кажется, что символы сокращаются в циклах описания ...; тест
Один маленький анализ:
источник
Japt
-¡
, 14 байтСохранено 3 байта благодаря @Shaggy
Попытайся
источник
ÎfUÌ l
или, еще короче,rf l
.rø
было бы самым коротким способом сделать это, но Оливер победил вас в этом.Желе ,
189 байтПопробуйте онлайн!
Спасибо @Jonathan Allan за -9 и потрясающей помощи :).
Принимает ввод как массив из двух элементов. Объяснение кода:
¹
источник
,
. ЭтоẒƇ
избыточно, нет простых простых факторов. ТогдаÆFḢ€
это справедливоÆf
, за исключением того, что последний дает нам повторения, которые нам могут понадобиться, например,26=2*13
и в125=5*5*5
то время2+13=5+5+5
. Даже с этим, однако,Ẇ
это не достаточно хорошо, например, вместо26
использования,182=2*7*13
которое также должно найти это,2+13=5+5+5
но не делает - вместо этого мы хотим power-set (ŒP
) без ведущего, пустого элемента (мы можем использоватьḊ
).S€
здесь можно заменить на§
. - Вы, вероятно, можете сохранить байты с помощью$
иƊ
-.)
и с моими исправлениями, чтобы заставить его работать правильно (плюс заменаœ&
наf
), код составляет 9 байтов:ÆfŒPḊ§)f/
try-itГея ,
1611 байтПопробуйте онлайн!
Функция top (первая строка) вычисляет суммы набора степеней простых множителей, а вторая функция находит, если какой-либо из элементов пересечения ненулевой.
источник