Wejście

Pojedyncza liczba całkowita . $1 \leq x \leq 10^{15}$

Wynik

Maksymalna liczba wyraźnych liczb całkowitych dodatnich, które mają iloczyn . $x$

Przykłady

Dane wejściowe: 1099511627776. Dane wyjściowe: 9. Jedną z możliwych optymalnych list czynników jest: (1, 2, 4, 8, 16, 32, 64, 128, 4096).

Dane wejściowe: 127381. Dane wyjściowe 4. Jedną z możliwych optymalnych list czynników jest: (1, 17, 59, 127).

Powiązane z tym starym pytaniem .

code-golf math

— Anush
źródło

9

Czy możesz dodać jeszcze kilka przypadków testowych? (Najlepiej rozsądnej wielkości.)

— Arnauld

8

Biorąc pod uwagę twoje komentarze do większości odpowiedzi: jeśli zamiast tego szukasz wydajnego kodu, zdecydowanie nie należy go oznaczać jako code-golf. Można rozważyć albo fastest-codeczy fastest-algorithmna nadchodzące wyzwania. Jeśli naprawdę chciałeś, aby wszystkie odpowiedzi działały w ograniczonym czasie w określonym zakresie, należy to wyraźnie zaznaczyć. (I zaleciłbym mniejszy zakres, aby nie był code-golfcałkowicie sprzeczny .)

— Arnauld

@Arnauld Nie Jestem ostrożny, aby uczynić go golfem i nikt nie jest za to oceniany. Byłoby po prostu fajnie, gdyby kod mógł działać dla określonych zakresów wejściowych.

— Anush

5

Cytując xnor: Jeśli nie jest to obowiązkowe, odpowiedzi tego nie zrobią .

— Arnauld

1

Bo x=1, 2, ...dostaję, f(x)=1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 3, 4, 2, 3czego nie znalazłem w OEIS. Jest wystarczająco jasne, że rekordy pojawią się dla liczb silni x. Na przykład najmniejszy xtaki, który f(x)=13będzie 13!. Myślę, że fzależy tylko od wykładników pierwszej faktoryzacji. Aby znaleźć, f(13^4*19^7*29^2)możemy uprościć f(2^7*3^4*5^2).

— Jeppe Stig Nielsen

5

Wolfram Language (Mathematica) , 52 bajty

Max[Length/@Cases[Subsets@Divisors@#,{a__}/;1a==#]]&

Wypróbuj online!

4 bajty zapisane dzięki @attinat

Tutaj jest także wersja 153-bajtowa, która oblicza 1099511627776i10^15

Max[Length/@Table[s=RandomSample@Flatten[Table@@@FactorInteger[#]];Last@Select[Times@@@TakeList[s,#]&/@IntegerPartitions@Length@s,DuplicateFreeQ],5!]]+1&

Wypróbuj online!

Wynik dla 10^15to 12

{1, 2, 4, 5, 10, 16, 25, 40, 50, 100, 125, 250}

— J42161217
źródło

Wywala z 1099511627776

— anuś

7

@Anush To się nie zawiesza. Po prostu potrzebuje pamięci. Nie mówiłeś nic o ograniczeniach pamięci. To jest kod golfowy

— J42161217

Tak, rozumiem. Byłoby po prostu miło, gdybyś mógł faktycznie uruchomić kod zakresów wejściowych określonych w pytaniu.

— Anush

6

@Anush To jest golf golfowy. Niezłe odpowiedzi. Proszę podać swoje kryteria. Odpowiedź jest poprawna lub nie. Myślę, że problemem jest pytanie ... Może powinieneś zmienić to na „najbardziej wystarczający algorytm”

— J42161217

3

@Anush Zrobiłem edycję w mojej odpowiedzi i dodałem jeszcze jedną wersję, która jest naprawdę szybka i wydajna na wypadek, gdybyś chciał to sprawdzić

— J42161217

4

Wolfram Language (Mathematica) , 38 bajtów

(c=n=#;If[i∣n,n/=i,--c]~Do~{i,n};c)&

Wypróbuj online!

Chciwy algorytm. Przekracza limit czasu TIO przy większych wejściach, takich jak 1099511627776.

— attinat
źródło

3

05AB1E , 9 bajtów

Bardzo nieefektywne. Przekroczę limit czasu na TIO dla liczb z dużą liczbą dzielników.

ÑæʒPQ}€gZ

Wypróbuj online!

Wyjaśnienie

Ñ          # push a list of divisors of the input
 æ         # push the powerset of that list
  ʒPQ}     # filter, keep only the lists whose product is the input
      €g   # get the length of each
        Z  # take the maximum

— Emigna
źródło

Twój kod TIO wydaje się wyprowadzać 3 zamiast 9.

— Anush

@Anush: Jest to inna liczba niż twój przykład (ponieważ jeden raz się z powodu wielu czynników). Prawdopodobnie powinienem użyć bardziej wyraźnego przykładu.

— Emigna

€gZjest nieco bardziej wydajny niż éθgdla tego samego bajtu.

— Grimmy,

@Grimy: True. Nie zrobi to dużej różnicy, ponieważ to filtr jest tutaj dużym złym facetem, ale nie zaszkodzi być trochę bardziej wydajnym :)

— Emigna

2

Perl 6 , 38 bajtów

{$!=$_;+grep {$!%%$_&&($!/=$_)},1..$_}

Wypróbuj online!

Podchodzi chciwie do wyboru dzielników.

— Jo King
źródło

Nie kończą się 1099511627776

— anuś

6

@Anush Cóż, ostatecznie się kończy . Zasadniczo odpowiedź jest poprawna, jeśli algorytm programu działałby z dowolnym wejściem, gdyby miał tyle pamięci i czasu, ile chciał. Ponieważ jest to golf golfowy , zoptymalizowałem go pod kątem długości kodu, a nie złożoności algorytmicznej

— Jo King

2

JavaScript (ES6), 39 bajtów

f=(n,i=0)=>n%++i?n>i&&f(n,i):1+f(n/i,i)

Prawdopodobnie jest kilka bajtów, które można zapisać tu i tam. Po prostu używa chciwego algorytmu dla czynników.

— vrugtehagel
źródło

2

Galaretka , 9 bajtów

ŒPP=³ƊƇẈṀ

Wypróbuj online!

-1 bajt dzięki komuś

-2 bajty dzięki ErikTheOutgolfer

— HyperNeutrino
źródło

Przygotowując dane wejściowe dla superseekera OEIS, stworzyłem prawdopodobnie 11-bajtowy program do gry w galaretkę (który wykorzystuje inne podejście) i raczej nie opublikuję odpowiedzi na galaretkę, więc udam, że grałem w bajt z twojego rozwiązania: ÆE×8‘½’:2S‘(to współpracuje z mocą sekcji „formuła” OEIS dla A003056). Oświadczenie: może być źle, ale działa na przypadkach testowych.

— mój zaimek to monicareinstate

Nie wydaje się, aby zakończyć z 1099511627776

— anuś

@someone nie działa przez 36, ale dzięki

— HyperNeutrino

@Anush tak, to jest naprawdę powolne, ponieważ grałem w golfa, nie zoptymalizowany pod kątem wydajności

— HyperNeutrino

1

ÆD

x \geq 21

$x\ge21$

2

Japt `-h` , 13 bajtów

â à f_×¶UÃmÊn

Spróbuj

— Wcielenie ignorancji
źródło

2

Brachylog , 8 bajtów

f;?⟨⊇×⟩l

Wypróbuj online!

(Naiwne podejście {~×≠l}ᶠ⌉generuje nieskończoną liczbę rozwiązań z dodatkowymi 1s przed ich wyeliminowaniem ≠, a tym samym nie kończy się. To jednak nie jest problem, ponieważ dotyczy tej samej liczby bajtów!)

Pobiera dane wejściowe przez zmienną wejściową i dane wyjściowe przez zmienną wyjściową. Nagłówek TIO zawiera kopię większości kodu w celu pokazania, czym jest lista czynników, ale bez tego działa ona doskonale. Ponieważ ⊇najpierw daje większe listy podrzędne, ten predykat zasadniczo robi to samo, co większość innych odpowiedzi, ale bez wyraźnego generowania i filtrowania pełnego zestawu czynników, dzięki cofnięciu.

            The output
       l    is the length of
    ⊇       a sublist (the largest satisfying these constraints)
f           of the factors of
            the input
 ; ⟨  ⟩     which
     ×      with its elements multiplied together
  ?         is the input.

— Niepowiązany ciąg
źródło

1

Scala , 77 bajtów

def f(n:Long)={var(m,c,i)=(n,1,2L);while(i<=m){if(m%i==0){m/=i;c+=1};i+=1};c}

Wypróbuj online!

— Piotr
źródło

1

Gaia , 10 9 bajtów

Π=
dz↑⁇(l

Wypróbuj online!

Podąża za tym samym „algorytmem”, jak pokazano gdzie indziej - najdłużej przefiltruj zestaw dzielników z iloczynem równym liczbie i zwróć jego długość.

	| helper function
Π=	| is prod(list)==n (implicit)?
	|
	| main function; implicitly takes n
dz	| divisor powerset (in decreasing order of size)
  ↑⁇	| filter by helper function
    (l	| take the first element and take the length (implicitly output)

— Giuseppe
źródło

0

Clam , 15 bajtów

p}_`nq#:;qQ@s~Q

Link do TIO już wkrótce (kiedy Dennis ściąga)

Zasadniczo port rozwiązania 05AB1E @ Emigna.

Wyjaśnienie

                - Implicit Q = first input
p               - Print...
 }              - The last element of...
  _             - Sorted...
   `nq          - Lengths of... (map q => q.len)
           @s   - Items in powerset of
             ~Q - Proper divisors of Q
      #         - Where... (filter)
        ;q      - Product of subset
       :        - Equals...
          Q     - Q

— Skidsdev
źródło

0

C # (interaktywny kompilator Visual C #) , 54 bajty

int f(int n,int i=0)=>n%++i<1?1+f(n/i,i):n>i?f(n,i):0;

Stosuje to samo podejście, co odpowiedzi @ vrugtehagel i @ JoKing.

Wypróbuj online!

— Wcielenie ignorancji
źródło

Zakładając, że poprawnie zaimplementowałem twoją logikę, 53-bajtowe rozwiązanie (że nie mogę pozbyć się słowa kluczowego „return”): Wypróbuj online!

— mój zaimek to monicareinstate

1

@someone Dzięki, ale według meta funkcje muszą być wielokrotnego użytku . Nie wiem też, czy dopuszczalne jest, aby deklaracje poza funkcją pomijały końcowy średnik, mogą w tym napisać meta.

— Embodiment of Ignorance

0

Rubinowy , 34 bajty

Oczywiście przekroczono limit czasu dla tej ogromnej liczby, ale ostatecznie upłynie limit czasu, jeśli będzie wystarczająco dużo czasu na innej maszynie.

->n{(1..n).count{|e|n%e<1?n/=e:p}}

Wypróbuj online!

— Wartość tuszu
źródło

Gra w faktoryzację

Wejście

Wynik

Przykłady

Wolfram Language (Mathematica) , 52 bajty

Wolfram Language (Mathematica) , 38 bajtów

05AB1E , 9 bajtów

Perl 6 , 38 bajtów

JavaScript (ES6), 39 bajtów

Galaretka , 9 bajtów

Japt -h , 13 bajtów

Brachylog , 8 bajtów

Scala , 77 bajtów

Gaia , 10 9 bajtów

Clam , 15 bajtów

Wyjaśnienie

C # (interaktywny kompilator Visual C #) , 54 bajty

Rubinowy , 34 bajty

Japt `-h` , 13 bajtów