Простые числа в главной факторизации

9

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

Оказывается, поставленный вопрос был тривиальным, но мне интересно, верно ли то же самое в отношении вопроса, который я (неправильно) прочитал:

6 может быть представлен 2 ^ 1 * 3 ^ 1, а 50 может быть представлен 2 ^ 1 * 5 ^ 2 (где ^ означает экспоненту).

Твое задание:

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

Входные данные:

Целое число n такое, что 1 <n <10 ^ 12, взятое любым нормальным методом.

Вывод:

Количество различных простых чисел, необходимых для представления уникальных простых множителей n.

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

Input      Factorisation      Unique primes in factorisation representation
24         2^3*3^1            2 (2, 3)
126        2^1*3^2*7^1        3 (2, 3, 7)
8          2^3                2 (2, 3)
64         2^6                1 (2) (6 doesn't get factorised further)
72         2^3*3^2            2 (2, 3)
8640       2^6*3^3*5^1        3 (2, 3, 5)
317011968  2^11*3^5*7^2*13^1  6 (2, 3, 5, 7, 11, 13)
27         3^3                1 (3)

Это не последовательность OEIS.

Подсчет очков:

Это Код-гольфвыигрывает самый низкий результат в байтах!

code-golf math primes integer pbeentje
источник
Для чего нужен ожидаемый результат 64? Это 2 (2,3)(как 6 можно представить как 2 * 3) или 1 (2)(игнорировать 6)?
Emigna
для 64ожидаемого результата 1 (2). Мне нравится идея делать это рекурсивно, но я не так читаю оригинальный вопрос. Я думал, что это 8640был подходящий тестовый пример, но должен был быть более явным - спасибо.
pbeentje
Вы утверждаете, что это не последовательность OEIS. Разве это не A001221, значения (маленькой) функции омега?
Грей Тейлор
A001221 аналогичен, но начинает расходиться в терминах 8 и 9 (здесь 2, A001221 1) из-за включения показателя степени в качестве простого в этом упражнении.
pbeentje
Ах я вижу. Запишите основную факторизацию, затем посмотрите, сколько разных простых чисел я написал (независимо от роли, которую они сыграли). Интересно, что произойдет, если вы пойдете на шаг дальше и факторизуете показатель ...
Грей Тейлор,

Ответы:

5

Mathematica, 39 байт

Count[Union@@FactorInteger@#,_?PrimeQ]&

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

спасибо Мартину Эндеру (-11 байт)

J42161217
источник
Casesоказывается короче Select(-4 байта): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(проходит все тестовые примеры на свежем ядре)
JungHwan Мин
Как насчет Count[Union@@FactorInteger@#,_?PrimeQ]&? (Не проверены все тестовые случаи.)
Мартин Эндер
@MartinEnder кажется, что это должно работать. Проходит все тестовые случаи тоже.
JungHwan Мин
5

05AB1E , 9 7 байт

Сохранено 2 байта благодаря Кевину Круйссену

ÓsfìÙpO

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

объяснение

Ó        # push the prime factor exponents of the input
 sfì     # prepend the prime factors of the input
    Ù    # remove duplicates
     p   # check each if it is prime
      O  # sum
Emigna
источник
1
-1 байт, используя €pOпосле слияния основных факторов и показателей:ÓsfìÙ€pO
Кевин Круйссен
@KevinCruijssen: Спасибо! На самом деле сохраняет 2, так €как не требуется.
Эминья
Ах, конечно .. Ух ты, не уверен, как я это пропустил, хаха xD
Кевин Круйссен
4

Желе ,  9  7 байт

ÆFFQÆPS

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

Как?

ÆFFQÆPS ~ Полная программа.

ÆF ~ Первичная факторизация в виде [простых, показательных] пар.
  F ~ Flatten.
   Q ~ Дедупликация.
    ~P ~ Для каждого проверьте, является ли оно простым. 1, если Истина, 0, если Ложь.
      Сумма
Мистер Xcoder
источник
4

Gaia , 6 байт

ḋ_uṗ¦Σ

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

  • ḋ вычисляет простую факторизацию в виде пар [простое, экспонента]

  • _ сглаживает список.

  • u удаляет дубликаты элементов

  • ṗ¦отображается через элементы и возвращает 1, если простое число найдено, 0 в противном случае.

  • Σ подводит итоги списка

Мистер Xcoder
источник
3

CJam (13 байт)

{mFe__&:mp1b}

Набор онлайн-тестов

Это довольно просто: получать простые числа с кратностями, сводить к разным значениям, фильтровать простые числа, считать.

К сожалению, Мартин указал на некоторые случаи, которые не были обработаны слегка интересным трюком в моем первоначальном ответе, хотя он также обеспечил 1-байтовое сохранение, наблюдая, что поскольку mpдает 0или 1это может быть отображено, а не отфильтровано.

Питер Тейлор
источник
0

J, 20 байт

3 :'+/1 p:~.,__ q:y'

Подсчитано рукой, лол, так скажи мне, если это не так.

Какие-нибудь предложения по игре в гольф?

Скучная подача: выровняйте таблицу простых чисел и посчитайте простые числа.

капуста
источник
0

Javascript (ES6), 145 байт

n=>{for(a=[b=l=0],q=n,d=2;q>=2;)q%d?(b&&(a.push(0),l++),d++,b=0):(q/=d,a[l]++,b=1);for(i in a){for(d=1,e=a[i];e%d;d++);e-d||n%e&&l++};return l+1}
Naruyoko
источник