Крупнейшие премьер-экспоненты

22

Учитывая целое число n >= 2, выведите наибольший показатель степени в ее первичной факторизации. Это последовательность OEIS A051903 .

пример

Пусть n = 144. Его главная факторизация есть 2^4 * 3^2. Самый большой показатель степени 4.

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

2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 1
7 -> 1
8 -> 3
9 -> 2
10 -> 1
11 -> 1
12 -> 2
144 -> 4
200 -> 3
500 -> 3
1024 -> 10
3257832488 -> 3
code-golf number-theory primes integer factoring Mego
источник
Песочница
Mego

Ответы:

4

Python 2 , 78 байт

n=input()
e=m=0
f=2
while~-n:q=n%f<1;f+=1-q;e=q*-~e;m=max(m,e);n/=f**q
print m

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

-5 благодаря овс .

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

Эрик Аутгольфер
источник
81 байт
овс
@ovs спасибо, пропустил это, пока я пытался опубликовать быстро
Эрик Outgolfer
78 байт
овс
@ovs наконец-то, расслабился от if / else, спасибо
Эрик Аутгольфер
4

Japt -h , 9 7 байт

k ü mÊn

Попытайся

k ü mÊn     :Implicit input of integer
k           :Prime factors
  ü         :Group by value
    m       :Map
     Ê      :  Length
      n     :Sort
            :Implicit output of last element
мохнатый
источник
2
Я чувствую, что это должно быть намного короче, может быть, я должен добавить встроенный для пар простых показателей ...
ETHproductions
Зачем использовать «ü: Группировать по значению» вместо функции сортировки? Да, возможно, потому что sort возвращает один массив, но нам нужен один массив массивов
RosLuP
1
@RosLuP, Точно; üсоздает подмассивы равных значений. Это делает также сортировать по стоимости первого , но это не имеет значения здесь.
Мохнатый
3

Mathematica, 27 байт

Max[Last/@FactorInteger@#]&

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

J42161217
источник
В качестве альтернативы Max@@Last/@FactorInteger@#&. К сожалению, это не спасает байты.
полностью человек
2

Javascript 54 байта

* при условии бесконечного стека (как это делается в задачах Code-Golf)

P=(n,i=2,k)=>i>n?k:n%i?k>(K=P(n,i+1))?k:K:P(n/i,i,-~k)

console.log(P(2 )== 1)
console.log(P(3 )== 1)
console.log(P(4 )== 2)
console.log(P(5 )== 1)
console.log(P(6 )== 1)
console.log(P(7 )== 1)
console.log(P(8 )== 3)
console.log(P(9 )== 2)
console.log(P(10 )== 1)
console.log(P(11 )== 1)
console.log(P(12 )== 2)
console.log(P(144 )== 4)
console.log(P(200 )== 3)
console.log(P(500 )== 3)
console.log(P(1024 )== 10)
//console.log(P(3257832488 )== 3)
Развернуть фрагмент

DanielIndie
источник
2

PARI / GP, 24 байта

n->vecmax(factor(n)[,2])

Если я не считаю n->часть, это 21 байт.

Джепп Стиг Нильсен
источник
2

Октава , 25 байт

@(n)[~,m]=mode(factor(n))

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

объяснение

factorпроизводит массив (возможно, повторяющихся) простых показателей. Второй вывод modeдает количество раз, когда появляется режим (т.е. наиболее повторяющаяся запись).

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

Gaia , 4 байта

ḋ)⌠)

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

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

    • ⌠ - Карта и собрать результат с максимальным значением.

    • ) - Последний элемент (показатель степени).

    • ) - Последний элемент (максимальный показатель)

Gaia , 4 байта

ḋ)¦⌉

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

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

    • )¦ - Карта с последним элементом (экспонента).

    • ⌉ - Получает максимальный элемент.

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

Октава : 30 байт

@(x)max(histc(a=factor(x),a));
  1. a=factor(x)возвращает вектор , содержащий простые множители x. Это вектор, отсортированный в порядке возрастания, где умножение всех чисел в factor(x)дает xсебя так, что каждое число в векторе является простым.
  2. histc(...,a)вычисляет гистограмму для вектора простого множителя, где ячейки являются основными множителями. Гистограмма подсчитывает, сколько раз мы видели каждое простое число, получая, таким образом, показатель степени каждого простого числа. Здесь мы можем немного обмануть, потому что, хотя мы factor(x)будем возвращать повторяющиеся числа или ячейки, только одна из ячейок будет отображать общее количество раз, когда мы видим простое число.
  3. max(...) таким образом возвращает наибольший показатель.

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

rayryeng - Восстановить Монику
источник
1

Алиса , 17 байт

/o
\i@/w].D:.t$Kq

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

объяснение

/o
\i@/...

Это просто структура для простых арифметических программ с десятичным вводом / выводом. ...Фактическая программа, которая уже имеет вход в стеке и оставляет выход на вершине стека.

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

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

w      Remember the current IP position. Effectively starts a loop.
  ]      Move the tape head to the right, which increments our counter.
  .D     Duplicate the current value, and deduplicate its prime factors.
         That means, we'll get a number which is the product of the value's
         unique prime factors. For example 144 = 2^4 * 3^2 would become
         6 = 2 * 3.
  :      Divide the value by its deduplicated version, which decrements the
         exponents of its prime factors.
  .t     Duplicate the result and decrement it. This value becomes 0 once we
         reach a result of 1, which is when we want to terminate the loop.
$K     Jump back to the beginning of the loop if the previous value wasn't 0.
q      Retrieve the tape head's position, i.e. the number of steps we've taken
       through the above loop.
Мартин Эндер
источник
1

Юлия, 60 52 40 байт

f(x)=maximum(collect(values(factor(x))))

-12 + коррекция благодаря Steadybox

EricShermanCS
источник
1
Я думаю, вам нужно добавить вызов print(). Кроме того, я не смог заставить код работать на TIO как есть, я полагаю, он работает на какой-то другой версии языка, недоступной там? Это прекрасно работает на print(maximum(collect(values(factor(parse(BigInt,readline()))))))
TIO
Это работает на переводчике (на моем компьютере, по крайней мере). Это также вызывает предупреждение, потому что инициализация подобного BigInt устарела. Тем не менее, если вы копируете и вставляете код как есть в интерпретатор Julia, он должен работать. (если печать требуется, потому что она должна быть явно напечатана, я плохо это подставлю)
EricShermanCS
1
Это print()необходимо, потому что ответом должна быть полная программа (отображающая вывод) или функция (возвращающая вывод). В противном случае ваше решение в порядке. Кажется, что вы можете сохранить несколько байтов (и избежать печати) следующим образом:f(x)=maximum(collect(values(factor(x))))
Steadybox
1
Пожалуйста! Вот мета-пост о том, что является разрешенным форматом для решения.
Steadybox
0

На самом деле , 4 байта

w♂NM

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

w♂NM - Полная программа.

w - толкает простую факторизацию в виде пар [простое, экспонента].
 ♂N - Получить последний элемент каждого (экспоненты).
   М - Максимум.
Мистер Xcoder
источник
Я использовал это точное решение для написания тестовых случаев :)
Mego
@Mego Как вы думаете, это может стать короче (я не хочу, чтобы вы испортили, если у вас есть более короткий, просто спрашиваю)? :)
Mr. Xcoder
Нет, я считаю, что это на самом деле оптимально.
Мего
0

Python 2 , 64 байта

-4 байта благодаря H.PWiz.

lambda n:max(a*(n%k**a<1)for a in range(n)for k in range(2,-~n))

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

Порт H.PWiz's Haskell ответ . Я делюсь этим только потому, что горжусь тем, что смог понять этот фрагмент кода на Haskell и перевести его. :П

totallyhuman
источник
Не range(1,n)работает?
H.PWiz
range(1, n)производит все целые числа в [1, n).
полностью человек
1
Ах, ну, на самом деле вам не нужно идти до п a
H.PWiz
О, хорошо, я не совсем понимаю математику за этим. : P Спасибо!
полностью человек
1
64 байта
H.PWiz
0

Аксиома, 61 байт

f n==(a:=factors n;reduce(max,[a.i.exponent for i in 1..#a]))

Впервые я обнаружил, что можно определить функцию без использования круглых скобок (). Вместо "f (n) ==" "fn ==" на один символ меньше ...

RosLuP
источник
0

рэкет , 83 79 байт

(λ(n)(cadr(argmax cadr((let()(local-require math/number-theory)factorize)n))))

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

(Я не уверен, что существует консенсус относительно того, что представляет собой полное решение Racket, поэтому я придерживаюсь соглашения Mathematica, что чистая функция считается.)

Как это работает

factorizeдает факторизацию как список пар: (factorize 108)дает '((2 2) (3 3)). Второй элемент пары задается cadrкак сокращение для композицииcar (заголовок списка) сcdr (хвост списка).

Я чувствую себя глупо, (cadr (argmax cadr list))чтобы найти максимум вторых элементов, ноmax не работает со списками:(max (map cadr list)) не делает то, что мы хотим. Я не эксперт в Racket, поэтому, возможно, есть стандартный лучший способ сделать это.

Ракетка, 93 байта

(λ(n)(define(p d m)(if(=(gcd m d)d)(+(p d(/ m d))1)0))(p(argmax(λ(d)(p d n))(range 2 n))n))

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

Как это работает

Альтернативная версия, которая не импортирует, factorizeа делает все с нуля, более или менее. Функция (p m d)находит наибольшую степень dделения, mа затем мы просто находим наибольшее значение (p n d)для dмежду 2и n. (Нам не нужно ограничивать это простыми числами, поскольку не будет составной силы, которая работает лучше, чем простые силы.)

Миша лавров
источник
Я думаю, стандартное maxрешение, (apply max (map cadr list)но (cadr (argmax cadr list)), к сожалению, короче.
Миша Лавров
0

APL (NARS), 15 символов, 30 байтов

{⌈/+/¨v∘=¨v←π⍵}

тест:

  f←{⌈/+/¨v∘=¨v←π⍵}
  f¨2..12
1 1 2 1 1 1 3 2 1 1 2 
  f¨144 200 500 1024 3257832488
4 3 3 10 3

комментарий:

{⌈/+/¨v∘=¨v←π⍵}
          v←π⍵    π12 return 2 2 3; assign to v the array of prime divisors of argument ⍵
      v∘=¨        for each element of v, build one binary array, show with 1 where are in v array, else puts 0 
                  return one big array I call B, where each element is the binary array above
   +/¨            sum each binary element array of  B
 ⌈/               get the max of all element of B (that should be the max exponet)
RosLuP
источник