Formuła

Weźmy na przykład liczbę 300

• Czynniki pierwsze 300 to [2, 3, 5](unikalne liczby, które są współczynnikami 300 i liczba pierwsza)
• Kwadrat każdej z tych liczb da ci [4, 9, 25]
• Podsumowanie tej listy da ci 4 + 9 + 25 = 38
• Na koniec odejmij tę sumę (38) od oryginalnego numeru 300-38 = 262(to wynik)

Wejście

Wprowadzona liczba będzie dodatnią liczbą całkowitą większą niż 2. Musisz sprawdzić wszystkie liczby od 2 do wartości wejściowej (włącznie) i znaleźć liczbę, która daje najlepszy wynik przy użyciu powyższej formuły.

Wynikiem będą dwie liczby oddzielone spacją, przecinkiem, znakiem nowej linii lub czymkolwiek innym językiem, na jaki pozwalasz (separacja jest niezbędna do rozróżnienia dwóch liczb). Można je wyprowadzić do pliku, standardowego wyjścia lub dowolnego innego języka. Twoim celem jest znalezienie liczby w zakresie, który daje maksymalną wydajność, gdy przejdziesz przez powyższą formułę. Pierwsza wyświetlana liczba powinna być liczbą początkową (np. 300), a druga liczba powinna stanowić wynik wygenerowany przez formułę (jak 262)

Input: 3       Output: 2, -2
Input: 10      Output: 8, 4
Input: 50      Output: 48, 35
Input: 1000    Output: 1000, 971
Input: 9999    Output: 9984, 9802

Rozważ wprowadzenie 10, musimy uruchomić formułę dla wszystkich liczb od 2 do 10 (włącznie)

Num PrimeFacs PrimeFacs^2 SumPrimeFacs^2 Result
2   [2]       [4]         4              -2
3   [3]       [9]         9              -6
4   [2]       [4]         4               0
5   [5]       [25]        25             -20
6   [2, 3]    [4, 9]      13             -7
7   [7]       [49]        49             -42
8   [2]       [4]         4               4
9   [3]       [9]         9               0
10  [2, 5]    [4, 25]     29             -19

Jak widać, najlepszy wynik to 4wynik wprowadzenia wartości 8do formuły. Oznacza to, że wyjście 10powinno mieć wartość wejściową8, 4

Punktacja i zasady

Obowiązują domyślne zasady dla wejść i wyjść: Domyślne dla Code Golf: Metody wejścia / wyjścia
Zabronione są standardowe luki: Luki, które są domyślnie zabronione
Zgłoszenia mogą być funkcjami lub pełnymi programami

Najkrótszy kod w bajtach wygrywa

Pyth, 17 15 bajtów

_eSttm,-ds^R2{P

Zestaw testowy.

Java 8 lambda, 247 239 233 225 224 219 198 161 znaków

Pomyślałem, że to musi być możliwe w przypadku mniej niż 300 znaków, ponieważ ... no wiesz ... Java!

I rzeczywiście jest to możliwe nawet w przypadku mniej niż 200 znaków!

m->{int n=1,u,f,F[],g,G=g=1<<31;for(;++n<=m;){u=n;F=new int[m+1];for(f=1;++f<=u;)u/=u%f<1?(F[f]=f--):1;f=0;for(int p:F)f+=p*p;g=n-f>g?(G=n)-f:g;}return G+","+g;}

Nie wiem, czy takie użycie importu jest uzasadnione, ale zakładam, że powinno być w porządku. Oto lambda nierozwinięta do klasy:

public class Q80507 {
    static String greatestAfterReduction(int maxNumber) {
        int number = 1, upper, factor, primeFactors[], greatestResult, greatestNumber = greatestResult = 1 << 31; // <-- Integer.MIN_VALUE;
        for (;++number <= maxNumber;) {
            // get unique primefactors
            upper = number;
            primeFactors = new int[maxNumber + 1];
            for (factor = 1; ++factor <= upper;)
                upper /= upper % factor < 1 ? (primeFactors[factor] = factor--) : 1;

            factor = 0;
            for (int prime : primeFactors)
                factor += prime * prime;

            greatestResult = number - factor > greatestResult ? (greatestNumber = number) - factor : greatestResult;
        }
        return greatestNumber + "," + greatestResult;
    }
}

Ustalenie pierwotnego czynnika opiera się na tej odpowiedzi . Kod wykorzystuje funkcjonalność zestawów, ponieważ zapisują każdą wartość tylko raz, więc nie muszę się już martwić o dodatkowe duplikaty. Reszta kodu jest dość prosta, po prostu po pytaniu.

Aktualizacje

Usunięto znak nowej linii z wyniku.

Dzięki @ogregoire za grę w golfa na liczbach całkowitych. MIN_VALUE do 1 << 31!

Po ponownym przejrzeniu kodu znalazłem jeszcze kilka miejsc, w których można grać w golfa.

Dzięki @Blue za lewę == 0 do <1!

Usunięto resztki białych znaków. Również do separacji potrzebny jest tylko jeden znak, więc nie musisz marnować jednego znaku.

Jeszcze raz dziękuję @ogregoire za wskazanie, że mogę zwrócić wartość zamiast wydrukować ją i złożyć deklaracje! To bardzo oszczędzało!

Dowiedziałem się, że mogę użyć trójki zamiast drugiej, aby zaoszczędzić jeszcze jeden znak.

Dzięki @AstronDan za niesamowite wykorzystanie tablicy, która oszczędza import. To dało mi również możliwość skrócenia pierwszego, jeśli do trójki.

Właściwie 21 bajtów

u2x;`;y;*@-`M;M;)@í@E

Wypróbuj online!

Wyjaśnienie:

u2x;`;y;*@-`M;M;)@í@E
u2x;                   push two copies of range(2, n+1) ([2, n])
    `      `M          map:
     ;                   duplicate
      y;                 push two copies of prime divisors
        *                dot product of prime divisors lists (equivalent to sum of squares)
         @-              subtract from n
             ;M;)      duplicate, two copies of max, move one copy to bottom of stack
                 @í    get index of max element
                   @E  get corresponding element from range

MATL , 18 bajtów

:"@tYfu2^s-]v2#X>w

Wypróbuj online!

Ostatni przypadek kompilatora online trwa zbyt długo, ale daje poprawny wynik (zajmuje to około 11 sekund na moim komputerze, działającym na Matlabie):

Wyjaśnienie

Proste zastosowanie opisanej procedury.

:         % Implicit input n. Range [1 2 ... n]
"         % For each
  @       %   Push that number
  tYfu    %   Duplicate. Prime factors. Unique values
  2^s-    %   Square. Sum of array values. Subtract
]         % End for each
v         % Concatenate stack contents into vertical vector
2#X>      % Max and arg max
w         % Swap. Implicit display         

C #, 194 bajtów

Mój pierwszy Code Golf :). Użyłem mojego ulubionego języka pomimo jego gadatliwości. Zacząłem od tego jako portu funkcji C # w Javie @ Frozn, ale znalazłem kilka sposobów dalszego zmniejszenia kodu dzięki optymalizacji.

string R(int a){int u,f,g,N=g=1<<31;for(int n=1;++n<=a;){u=n;int[]P=new int[a+1];for(f=1;++f<=u;){if(u%f<1){u/=f;P[f]=f--;}}f=0;foreach(var p in P){f+=p*p;}if(n-f>g){g=(N=n)-f;}}return N+","+g;}

To używa tablicy do przechowywania czynników głównych. Ponieważ jest indeksowany przez czynnik, zastąpi powtarzające się czynniki kopiami tego czynnika. Dzięki temu funkcja nie ma importu. To nawet nie wymaga systemu.

Narzędzia Bash + GNU, 74

seq 2 $1|factor|sed -r 's/:?( \w+)\1*/-\1*\1/g'|bc|nl -v2|sort -nrk2|sed q

• seq generuje wszystkie liczby całkowite od 2 do n
• factorpodaje liczbę, po której następuje dwukropek, a następnie rozdzieloną spacjami listę wszystkich czynników pierwszych, w tym duplikatów. np. wynik dla 12 to12: 2 2 3
• sedusuwa dwukropek i duplikaty czynników, a następnie generuje wymagane wyrażenie arytmetyczne. np. dla 12:12- 2* 2- 3* 3
• bc ocenia to
• nl prefiksy n z powrotem (od 2)
• sort według drugiej kolumny, numerycznie, w porządku malejącym
• seq wypisuje pierwszą linię i wychodzi.

Ideone.

Brachylog , 48 bajtów

:2:{eI$pd:{:2^.}a+:I--:I.}fF$\hor:0m:Ir.r~m[F:J]

Wyjaśnienie

Main predicate:

:2:{}fF                     Unify F with the list of all binding for which predicate 1 is
                            true, given [Input, 2] as input.
       $\hor:0m             Retrieve the max of F by diagonalizing it, taking the
                            first row, sorting that row and reversing the sorted row.
               :Ir.         Unify the Output with [I, Max],
                   r~m[F:J] [I, Max] is in F at index J (the index is unimportant)


Predicate 1:

eI                          I is an integer in the range given in Input
  $pd                       Get the list of prime factors of I, with no duplicates
     :{:2^.}a               Apply squaring to each element of that list
             +              Sum the list
              :I-           Subtract I from the sum
                 -          Multiply by -1 (let's call it Result)
                  :I.       Unify the Output with [Result, I]

Galaretka , 13 bajtów

ÆfQ²S_@,µ€ḊṀṚ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

ÆfQ²S_@,µ€ḊṀṚ  Main link. Argument: n

        µ      Combine the chain to the left into a link.
         €     Apply it to each k in [1, ..., n].
Æf               Yield k's prime factors as a list.
  Q              Unique; deduplicate the prime factors.
   ²             Square each unique prime factor.
    S            Compute their sum.
     _@          Subtract the result from k.
       ,         Pair with k, yielding [result(k), k].
          Ḋ    Dequeue; discard the first pair which corresponds to k = 1.
           Ṁ   Get the maximum (lexicographical order).
            Ṛ  Reverse the pair.

05AB1E, 19 17 16 bajtów

Kod:

L©f€n€O®-®)ø¦{¤R

Wyjaśnienie:

L                    # make a list of 1..input [1,2,3,4,5,6]
 ©                   # save the list for reuse
  f                  # get primefactors of numbers in list [[],[2],[3],[2],[5],[2,3]]
   €n                # square each factor [[],[4],[9],[4],[25],[4,9]]
     €O              # sum the factors [0,4,9,4,25,13]
       ®-            # subtract from saved list [1,-2,-6,0,-20,-7]
         ®)ø         # zip with saved list [[1,1],[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
            ¦        # drop the first item (n=1) [[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
             {       # sort [[-20,5],[-7,6],[-6,3],[-2,2],[0,4]]
              ¤      # get last item [0,4]
               R     # reverse [4,0]

Wypróbuj online

Julia, 56 bajtów

!n=maximum(k->(k-sumabs2(k|>factor|>keys),k),2:n)[[2,1]]

Wypróbuj online!

Jak to działa

Biorąc pod uwagę wartość wejściową n , dla każdej liczby całkowitej k takiej, że 2 ≤ k ≤ n , generujemy krotkę (f (k), k) , gdzie f (k) jest różnicą między k a sumą kwadratów jej czynników pierwszych .

f (k) oblicza się za pomocą tego k-sumabs2(k|>factor|>keys), który uwzględnia k w Dyktat liczb pierwszych i wykładników, wyodrębnia wszystkie klucze (czynniki pierwsze), pobiera sumę ich kwadratów i odejmuje wynikową liczbę całkowitą od k .

Na koniec bierzemy maksimum leksykograficzne wygenerowanych krotek i odwracamy je, uzyskując dostęp do wskaźników 2 i 1 .

Clojure, 215 bajtów

(fn j[x](apply max-key second(map(fn[w][w(- w(let[y(reduce +(map #(* % %)(set(flatten((fn f[q](let[c(filter(fn[r](=(mod q r)0))(range 2 q))](if(empty? c)q(map f c))))w)))))](if(= y 0)(* w w)y)))])(range 2(inc x)))))

Po prostu przestrzega zasad. Oblicza czynniki pierwsze każdej liczby, oblicz je i zsumuj. Następnie wygeneruj listę wektorów 2 elementów: liczby początkowej i jej wyniku i znajdź element o maksymalnej wartości drugiego elementu.

Możesz to zobaczyć online tutaj: https://ideone.com/1J9i0y

R 109 bajtów

y=sapply(x<-2:scan(),FUN=function(x)x-sum(unique(as.numeric(gmp::factorize(x))^2)));c(x[which.max(y)],max(y))

I oszukany i używane pakietu gmp.

CJam, 32 bajty

ri({))_mf_|2f#:+-}/]_:e>_@#))\]p

Wypróbuj online!

Pyke, 17 bajtów

FODP}mXs-)DSei@Oi

Wypróbuj tutaj!

PowerShell v2 +, 124 120 117 bajtów

2..$args[0]|%{$y=$z=$_;2..$_|%{$y-=$_*$_*!($z%$_)*('1'*$_-match'^(?!(..+)\1+$)..')};if($y-gt$o){$o=$y;$p=$_}}
"$p $o"

Pierwszy wiersz oblicza wartości, drugi to tylko wynik.

Zaczynamy od utworzenia zakresu od 2naszego argumentu wiersza poleceń $args[0]i zapętlamy go |%{...}. W każdej pętli ustawiamy zmienne pomocnicze równe naszej bieżącej wartości $y=$z=$_. Następnie przeglądamy każdy numer od 2naszego obecnego numeru. W każdej wewnętrznej pętli sprawdzamy, czy liczba ta jest dzielnikiem !($z%$_)i czy jest liczbą pierwszą ('1'*$_-match'^(?!(..+)\1+$)..') , a jeśli obie, odejmujemy kwadrat $y(kontrole są wykonywane przy użyciu mnożenia logicznego).

Po przejściu przez wszystkie podstawowe dzielniki i odjęciu kwadratów, jeśli pozostała liczba jest największa, jaką widzieliśmy do tej pory $y-gt$o, ustawiamy nasze zmienne wyjściowe $o=$y;$p=$_. Po przejściu przez cały zakres po prostu wyprowadzamy z odstępem między.

Haskell, 91 bajtów

f m=reverse$maximum[[n-sum[p^2|p<-[2..n],mod n p<1,mod(product[1..p-1]^2)p>0],n]|n<-[2..m]]

Przykład użycia: f 50-> [48,35].

Funkcje współczynnika głównego są dostępne tylko za pośrednictwem, import Data.Numbers.Primesktóre kosztują zbyt wiele bajtów, więc używam sprawdzania liczb pierwszych @ Lynn . Reszta jest prosta: dla wejścia mpętli nprzez [2..m]w wewnętrznej pętli pprzez [2..n]. Zachowaj wszystko, pco najważniejsze, dziel n, kwadrat i suma.

Python 2, 108 105 100 bajtów

f=lambda n,m=2,p=1:m>n or-~f(n,m+1,p*m*m)-(n%m<p%m)*m*m
r=max(range(2,input()+1),key=f)
print r,f(r)

Przetestuj na Ideone .

JavaScript (ES6), 111 105 bajtów

f=n=>{r=n<2?[]:f(n-1);for(s=[],j=n,i=2;j>1;k%i?i++:j/s[i]=i);s.map(i=>j-=i*i,j=n);return j<r[1]?r:[n,j]}

Nie mam pojęcia, dlaczego wcześniej nie myślałem o tym rekurencyjnie.

J, 44 bajty

[:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.

Proste podejście. Zwraca również wszystkie wartościn tego wyniku w maksymalnej wartości.

Stosowanie

   f =: [:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.
   f 3
2 _2
   f 10
8 4
   f 50
48 35
   f 1000
1000 971
   f 9999
9984 9802
   f 950
900 862
945 862