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

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

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

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

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

Выход:

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

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

24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

Это OEIS A001221 .

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

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

code-golf number-theory primes integer грифон
источник

3

Так много важных вопросов в последнее время! Я люблю это.

Джузеппе

2

Связанные

г-н Xcoder

3

Причиной понижения может быть его банальность. Насколько я мог видеть, есть три ситуации, когда речь идет о языках игры в гольф: 1. встроенный 2. цепочка из двух встроенных 3. цепочка из 3 встроенных (лично у меня три двухбайтовых ответа); Я не знаю, является ли это веской причиной для отрицательного голоса, но это возможная причина

г-н Xcoder

1

Может быть, но я был бы признателен, если бы один из трех downvoters прокомментировал бы мне это. Хотя это является тривиальным на языках гольфа, есть несколько интересных решений в непроизведенных языках гольфа, которые являются те , которые я хотел бы видеть , когда я отвечал на этот вызов. В конце концов, на сайте есть много проблем, которые тривиальны для игры в гольф, но дают интересные решения, не связанные с гольфом.

Грифон

1

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

Деннис

6

MATL , 4 3 байта

-1 байт благодаря Луису Мендо

YFz

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

YF         Exponents of prime factors
  z        Number of nonzeros

Оригинальный ответ:

Yfun

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

Вер Yfunответ.

          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)

Giuseppe
источник

1

Почему весело? - ;-)

Adám

1

Вычеркнуто 4 все еще регулярно 4

Gryphon

5

05AB1E , 2 байта

^{еще один довольно скучный ответ ...}

fg

Полная программа, принимающая числовой ввод и печатающая результат

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

Как?

fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print

Джонатан Аллан
источник

5

Mathematica, 7 байтов

PrimeNu

Да, есть встроенный.

Mathematica, 21 байт

Length@*FactorInteger

Долгий путь вокруг.

Миша лавров
источник

В чем причина звездочки? Не Length@FactorIntegerто же самое?

Числовой маньяк

1

Length@*FactorIntegerпроизводит чистую функцию: состав Lengthи FactorInteger. Я могу определить, fun=Length@*FactorIntegerа затем позвонить fun[1001]. С другой стороны, Length@FactorIntegerбудет означать Length[FactorInteger]и оценивать 0.

Миша Лавров

5

Gaia , 2 байта

^{Еще один довольно скучный ответ ... --- Дж. Аллан}

ḋl

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

ḋ- Первичная факторизация в виде [простых, показательных] пар.
l - длина

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

4

Python 2, 56 байт

f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]

orlp
источник

Это порт Денниса ответ здесь случайно?

Джонатан Аллан

1

@JonathanAllan Да, модифицировано для подсчета уникальных простых факторов.

17

4

Сетчатка , 31 30 байт

&`(?!(11+)\1+$)(11+)$(?<=^\2+)

Ввод одинарный.

Спасибо @MartinEnder за игру в 1 байт!

Попробуйте онлайн!(включает десятичный в унарный преобразователь)

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

Поскольку программа состоит из одного регулярного выражения с &модификатором, Retina просто считает количество совпадений . Предполагается, что вход состоит из n повторений 1 и ничего больше.

Негативный взгляд

(?!(11+)\1+$)

совпадения в позициях между 1 , за которыми не следуют два или более 1 ( 11+), за которыми следуют одно или несколько повторений с одинаковым количеством 1 ( \1+), за которым следует конец ввода ($ ).

Любое составное число ab с a, b> 1 может быть записано как b повторений с повторениями 1 , так что предварительный просмотр соответствует только местоположениям, за которыми следуют p повторений 1 , где p = 1 или p является простым числом.

Регулярное выражение

(11+)$

удостоверится, что p> 1 , требуя, по крайней мере, два 1 ( 11+) и сохранит хвост 1 во второй группе захвата ( \2).

Наконец, позитивный взгляд за

(?<=^\2+)

проверяет, что весь вход состоит из kp вхождений ( k ≥ 1 ) из 1 , проверяя, что p делит вход.

Таким образом, каждому совпадению соответствует единственный простой делитель p .

Деннис
источник

4

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

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

factor|grep -Po ' \d+'|uniq|wc -l

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

объяснение

factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines

Цифровая травма
источник

1

grep -Po ' \d+'сохраняет байты над tr \ \\n|sed 1d.

Деннис

К сожалению, grep -Po '( \d+)\1*'не удается ввести 46 .

Деннис

@Dennis спасибо - я исправил это, используя ваше оригинальное предложение

Digital Trauma

3

Желе , 3 байта

^{довольно скучный ответ ...}

ÆFL

Монадическая ссылка, принимающая число и возвращающая число

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

Как?

ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length

Джонатан Аллан
источник

1

Как ты скучал Æv?

мое местоимение monicareinstate

Это было легко - я никогда не пользовался этим и не искал список в вики.

Джонатан Аллан

Как вы печатаете желейные символы без списка атомов и списка быстрых ответов?

мое местоимение monicareinstate

1. Æэто альтернативный код 0198. 2. Вы можете настроить клавиатуру (у меня нет). 3. Кодовая страница.

Джонатан Аллан

3

Ом v2 , 2 байта

ml

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

Две встроенные функции находятся рядом друг с другом в документации.

totallyhuman
источник

3

Желе , 2 байта

^{Еще один довольно скучный ответ ... --- Дж. Аллан}

Æv

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

Встроенный.

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

3

Алиса , 10 байт

/o
\i@/Dcd

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

объяснение

/o
\i@/...

Это просто стандартная структура для линейных арифметических программ, требующих десятичного ввода-вывода. Сама фактическая программа тогда просто:

Dcd

Который делает:

D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.

Мартин Эндер
источник

3

JavaScript 45 байт

* Для @SEJPM запросите объяснение: то, что я делаю здесь, это то, что я иду от 2 - n (который изменяется, и в конечном итоге будет наибольшим простым множителем) - теперь, если текущее число делит n, я хочу посчитать его только один раз (даже хотя это может быть коэффициент 2 * 2 * 2 * 3 - 2 считается один раз) - поэтому на рисунке появляется «j», когда j не указан в вызове функции - j получит значение « undefined ", и когда n% i == 0, тогда я вызываю функцию с j = 1 в следующем вызове) - и тогда я добавляю только 1, когда j равно undefined, что является! j + Function (n / i, i, ( j = 1 или просто 1)). я не изменяю i в этом вопросе, потому что он все еще может делиться на i снова (2 * 2 * 3), но тогда j будет равно 1, и это не будет учитываться как фактор. надеюсь, я объяснил это достаточно хорошо.

P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);

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

если последнее простое число очень велико, то оно будет иметь максимальный стек вызовов - если это проблема, я могу сделать итеративную

DanielIndie
источник

Не могли бы вы написать объяснение этого ответа? Кажется, используется обычный подход из остальных ответов.

SEJPM

@SEJPM я добавил там какое-то объяснение

DanielIndie

1

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

Джонатан Аллан

3

CJam , 7 5 байтов

Спасибо Мартину Эндеру за 2 байта!

{mF,}

Анонимный блок (функция), который ожидает входной номер в стеке и заменяет его выходным номером.

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

объяснение

{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length

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

3

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

ḋdl

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

объяснение

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Fatalize
источник

2

Pyth, 3 байта

l{P

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

Длина ( l) множества ( {) простых факторов ( P) входных данных.

isaacg
источник

2

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

Lup

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

объяснение

  p  -- prime factors
 u   -- unique elements
L    -- length

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

2

Фактически , 2 байта

^{Еще один довольно скучный ответ ... --- Дж. Аллан}

yl

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

Первый символ может быть заменен на w.

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

Этого достаточно, чувак ...: P

полностью человек

@icrieverytim Я обещаю , что это мой последний гольф -языка ответ ( у меня только 4: P)

г Xcoder

2

Пайк , 3 байта

P}l

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

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

2

Python 3 , 68 67 байт

1 байт удален благодаря @ Mr.Xcoder

lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

Это время для самых больших тестов. Попробуйте онлайн!

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

67 байт

г-н Xcoder

2

R + числа, 30 14 байтов

16 байтов удалено благодаря @Giuseppe

numbers::omega

Кроме того, вот Попробуйте онлайн! ссылка на @Giuseppe.

Джозеф Вуд
источник

Вы можете опустить f=function(x)и (x)как уже numbers::omegaявляется функцией. Однако, как numbersэто не является стандартным для R, вы должны сделать ответ «R + числа». Кроме того, вы должны включить ссылку TIO . Тем не менее +1 очень приятно.

Джузеппе

@ Джузеппе, ты слишком милая. Спасибо за вашу помощь. Кстати, в дополнение к некоторым твоим проницательным ответам я проверил советы по игре в гольф в R , как ты и предлагал. Там есть настоящие жемчужины. В любом случае, я обновлю свой ответ вашими рекомендациями. Кроме того, ваше MATLрешение очень хорошее (+1 вчера).

Джозеф Вуд

NP, не стесняйтесь пинговать меня в чате или комментировать мой ответ, если у вас есть вопросы.

Джузеппе

@Giuseppe Есть ли мета-консенсус в отношении необходимости явно указывать "R + числа"? Кажется, что если мы установим дополнительный пакет, то мы сможем сохранить байты явного вызова его сnumbers:: . В противном случае, для меня это то же самое, что и использование importлюбого другого языка.

BLT

(прокручивает вниз и видит пример этого на python ...) Наверное, меня интересует более широкий мета-консенсус. Это просто кажется мне глупым.

BLT

1

Выпуклый , 3 байта

mF,

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

GamrCorps
источник

1

Pari / GP , 5 байт

Я не знаю, почему это называется nu в Mathematica, а омега в Pari / GP.

omega

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

alephalpha
источник

1

Haskell , 58 байт

-4 байта благодаря @Laikoni

f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

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

объяснение

По существу генерирует все простые числа не более, чем nи фильтрует их как фактор n, а затем принимает длину результата.

f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number

SEJPM
источник

Ты можешь использовать sum[1|x<- ... ] вместо length.

Лайкони

1

Japt, 5 4 байта

â èj

Попытайся

Получите делители ( â) и посчитайте ( è) простых чисел ( j).

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

1

ARBLE , 28 байт

len(unique(primefactors(n)))

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

Это очень буквальное решение

Ataco
источник

Я смотрел на это и говорил: «Эй, подожди минутку, это фрагмент!» И тогда я вижу ... это должен быть неэзотерический язык с неявным IO ?!

полностью человек

@icrieverytim Поздравляем, вы обнаружили одну из главных причин существования этого языка.

ATaco

0

Дьялог АПЛ , 17 байт

⎕CY'dfns'
≢∪3pco⎕

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

Уриэль
источник

0

Python 2 , 63 55 байт

^{Гораздо более интересный ответ ...}

-8 байт благодаря Джонатану Фреху (используйте аргумент со значением по умолчанию для пост-корректировки результата простых чисел от 0до 1- намного лучше, чем лямбда-обертка !!)

f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

Рекурсивная функция, принимающая положительное целое число nи возвращающая положительное целое число.

Попробуйте онлайн! Действительно неэффективно, даже не беспокойтесь о других тестах.

Джонатан Аллан
источник

55 байтов .

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

@JonathanFrech Спасибо, это намного чище.

Джонатан Аллан

0

J, 12 байт

{:@$@(__&q:)

q: является функцией простых показателей J, давая ей аргумент __ создает матрицу, первая строка которой - все ненулевые простые множители, а вторая строка - их показатели.

Мы принимаем форму $ этой матрицы - строки за столбцами - количество столбцов является ответом, который мы ищем.

{: дает нам последний элемент этого списка двух элементов (количество строк, количество столбцов) и, следовательно, ответ.

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

Ион
источник

0

Java (OpenJDK 9) , 67 байт

n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

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

Оливье Грегуар
источник

0

Javascript ES6, 56 символов

n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

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

f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")

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

Qwertiy
источник

Сколько уникальных простых чисел?

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

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

Выход:

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

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

Ответы:

MATL , 4 3 байта

05AB1E , 2 байта

Как?

Mathematica, 7 байтов

Mathematica, 21 байт

Gaia , 2 байта

Python 2, 56 байт

Сетчатка , 31 30 байт

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

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

объяснение

Желе , 3 байта

Как?

Ом v2 , 2 байта

Желе , 2 байта

Алиса , 10 байт

объяснение

JavaScript 45 байт

CJam , 7 5 байтов

объяснение

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

объяснение

Pyth, 3 байта

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

объяснение

Фактически , 2 байта

Пайк , 3 байта

Python 3 , 68 67 байт

R + числа, 30 14 байтов

Выпуклый , 3 байта

Pari / GP , 5 байт

Haskell , 58 байт

Japt, 5 4 байта

ARBLE , 28 байт

Дьялог АПЛ , 17 байт

Python 2 , 63 55 байт

J, 12 байт

Java (OpenJDK 9) , 67 байт

Javascript ES6, 56 символов