Формула

Возьмите, например, число 300

• Основные факторы 300 [2, 3, 5](уникальные числа, которые являются факторами 300 и простые)
• Квадрат каждого из этих чисел даст вам [4, 9, 25]
• Суммирование этого списка даст вам 4 + 9 + 25 = 38
• Наконец, вычтите эту сумму (38) из вашего исходного числа 300-38 = 262(это результат)

вход

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

Ваш вывод будет двумя числами, разделенными пробелом, запятой, переводом строки или чем-то, что позволяет ваш язык (разделение необходимо для различения двух чисел). Они могут быть выведены в файл, стандартный вывод или на любой другой язык. Ваша цель состоит в том, чтобы найти число в диапазоне, которое дает максимальный выход при выполнении по формуле выше. Первое отображаемое число должно быть начальным числом (например, 300), а второе число должно быть выводом, полученным по формуле (например, 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

Рассмотрим ввод 10, мы должны запустить формулу для всех чисел от 2-10 (включительно)

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

Как вы можете видеть, наибольший результат 4, который был результатом ввода значения 8в формулу. Это означает, что вывод для ввода 10должен быть8, 4

Оценка и правила

Применяются правила по умолчанию для входов и выходов: по умолчанию для Code Golf: методы ввода / вывода
. Стандартные лазейки запрещены: лазейки , которые запрещены по умолчанию.
Представления могут быть функциями или полными программами.

Самый короткий код в байтах выигрывает

Pyth, 17 15 байт

_eSttm,-ds^R2{P

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

Java 8 лямбда, 247 239 233 225 224 219 198 161 символов

Я думал, что это возможно в менее чем 300 символов, потому что ... вы знаете ... Java!

И это действительно возможно даже в менее чем 200 символов!

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;}

Я не знаю, является ли это использование импорта законным, но я предполагаю, что все должно быть в порядке. Вот лямбда, разряженная в класс:

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;
    }
}

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

Обновления

Удален перевод строки из вывода.

Спасибо @ogregoire за игру в Integer.MIN_VALUE до 1 << 31!

Посмотрев код снова, я нашел еще несколько мест, где можно играть в гольф.

Спасибо @Blue за трюк от == 0 до <1!

Удалены некоторые оставшиеся пробелы. Также для разделения нужен только один символ, поэтому не нужно тратить один символ.

Еще раз спасибо @ogregoire за указание на то, что я могу вернуть значение вместо того, чтобы распечатать его и собрать объявления! Это спасло много!

Обнаружил, что могу использовать троичного вместо второго, если сохранить еще один символ.

Спасибо @AstronDan за потрясающее использование массива, который сохраняет импорт. Это также дало мне возможность сократить первый, если в тройной.

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

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

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

Объяснение:

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 байт

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

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

Последний случай занимает слишком много времени для онлайн-компилятора, но он дает правильный результат (это занимает около 11 секунд на моем компьютере, работающем на Matlab):

объяснение

Прямое применение описанной процедуры.

:         % 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 байта

Мой первый Код Гольф :). Я использовал свой любимый язык, несмотря на его многословие. Я начал это как порт функции C # Java @ Frozn, но нашел несколько способов дальнейшего сокращения кода за счет оптимизации.

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;}

Это использует массив для хранения основных факторов. Поскольку он индексируется фактором, он заменяет повторяющиеся факторы на копии фактора. Это позволяет функции не иметь импорта. Это даже не требует системы.

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

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

• seq генерирует все целые числа от 2 до n
• factorдает число, за которым следует двоеточие, а затем разделенный пробелами список всех простых факторов, включая дубликаты. например, результат для 1212: 2 2 3
• sedудаляет двоеточие и дубликаты факторов, затем генерирует необходимое арифметическое выражение. например, для 12:12- 2* 2- 3* 3
• bc оценивает это
• nl префиксы n обратно (начиная с 2)
• sort по второму столбцу численно в порядке убывания
• seq печатает первую строку и выходит.

Ideone.

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

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

объяснение

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]

Желе , 13 байт

ÆfQ²S_@,µ€ḊṀṚ

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

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

Æ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 байтов

Код:

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

Объяснение:

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]

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

Юлия, 56 байт

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

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

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

При заданном входном n для каждого целого числа k, такого что 2 ≤ k ≤ n , мы генерируем кортеж (f (k), k) , где f (k) - это разность между k и суммой квадратов его простых множителей. ,

Само по себе вычисляется f (k)k-sumabs2(k|>factor|>keys) , который переводит k в Dict простых ключей и значений экспонент, извлекает все ключи (простые множители), берет сумму их квадратов и вычитает полученное целое число из k .

Наконец, мы берем лексикографический максимум сгенерированных кортежей и обращаем его к нему, используя индексы 2 и 1 .

Clojure, 215 байтов

(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)))))

Просто следует правилам. Вычисляет главные факторы каждого числа, помещает их в квадрат и суммирует их. После этого создайте список векторов из 2 элементов: начальное число и его результат и найдите элемент с максимальным значением второго элемента.

Вы можете увидеть это онлайн здесь: https://ideone.com/1J9i0y

R 109 байт

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

Я обманул и использовал пакет gmp.

CJam, 32 байта

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

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

Пайк, 17 байт

FODP}mXs-)DSei@Oi

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

PowerShell v2 +, 124 120 117 байт

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

Первая строка вычисляет значения, вторая просто вывод.

Мы начинаем с создания диапазона 2вплоть до аргумента командной строки $args[0]и зацикливаем его |%{...}. В каждом цикле мы устанавливаем вспомогательные переменные, равные нашему текущему значению $y=$z=$_. Затем мы перебираем все номера 2вплоть до нашего текущего номера. В каждом внутреннем цикле мы проверяем, является ли это число делителем !($z%$_)и является ли оно простым ('1'*$_-match'^(?!(..+)\1+$)..') , и, если оно и то и другое, мы вычитаем квадрат из $y(проверки выполняются с использованием логического умножения)

Как только мы прошли все простые делители и вычли квадраты, если оставшееся число является наибольшим из тех, что мы видели до сих пор $y-gt$o, мы устанавливаем наши выходные переменные $o=$y;$p=$_. После того, как мы перебрали весь диапазон, мы просто выводим пробел между ними.

Haskell, 91 байт

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]]

Пример использования: f 50-> [48,35].

Функции простого множителя доступны только через import Data.Numbers.Primesстоимость, которая стоит слишком много байтов, поэтому я использую простейшую проверку @ Lynn . Остальное прямо вперед: для ввода mпетли nчерез [2..m]и во внутреннем цикле pчерез [2..n]. Держите все, pчто простое и делить n, квадрат и сумма.

Python 2, 108 105 100 байт

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)

Проверьте это на Ideone .

JavaScript (ES6), 111 105 байт

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]}

Понятия не имею, почему я не думал делать это рекурсивно раньше.

J, 44 байта

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

Прямой подход. Также возвращает все значения nэтого результата в максимальном значении.

использование

   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