Практикуюсь в решении задачек в Codewars.
Застопорился на следующей:
Есть число, например, 42
. Его делителями являются числа 1, 2, 3, 6, 7, 14, 21, 42
. Сумма квадратов всех делителей равна 2500
. А 2500
, в свою очередь, является квадратом целого числа 50
.
Так вот, на вход функции мы подаем промежуток чисел от m
до n
. Необходимо написать алгоритм, который в промежутке от m
до n
найдет все такие целые числа, которые бы соответствовали указанным выше условиям - сумма квадратов их делителей должна сама быть квадратом целого числа.
Функция возвращает массив массивов - например, в промежутке от 1 до 250 три числа соответствуют условиям, а выходе получим массив [[1, 1], [42, 2500], [246, 84100]]
, где первое число - само удовлетворяющее условиям число, а второе - сумма квадратов его делителей.
Если что, сама задачка: https://www.codewars.com/kata/55aa075506463dac6600010d
Я написал вполне работающий алгоритм. Однако Codewars иногда отклоняет решения, если считает алгоритм неэффективным. Для повышения эффективности алгоритма я сделал две его модификации:
- У числа не бывает целочисленного делителя больше, чем половина этого числа, поэтому выходим из цикла
for
, когда проходим половину числа - Если число нечетное, то все его делители тоже нечетные, поэтому при проверке нечетного числа в цикле for движемся с шагом 2:
1,3,5
и т.д.
Несмотря на это, мой алгоритм Codewars отклоняет. Подскажите, пожалуйста, как возможно ещё улучшить скорость этого алгоритма? Возможно я выбрал неправильный подход к решению? И второй вопрос, вытекающий из моих оптимизаций. Я напихал много различных проверок на чётность, на то, больше число половины проверяемого числа или нет. Насколько оно стоит того, может, эти проверки только замедляют код, а не избавляют программу от лишних вычислений?
Код:
fun listSquared(m: Long, n: Long): String {
var finalArray = mutableListOf<List<Long>>()
var sum: Long
for (i in m..n){
sum = 0
if (i % 2 == 0L){
for (j in 1..i){
if (i % j == 0L){
sum += j.toDouble().pow(2).toLong()
if (i/j < 2) break // у числа не бывает делителя больше, чем половина этого числа
}
}
} else {
for (j in 1..i step 2){ // если число нечетное, то все его делители тоже нечетные
if (i % j == 0L){
sum += j.toDouble().pow(2).toLong()
if (i/j < 2) break
}
}
}
if ((sqrt(sum.toDouble()) % 1.0) == 0.0){
finalArray.add(listOf(i, sum))
}
}
return finalArray.toString()
}
j.toDouble().pow(2).toLong()
, пожалуйста, не делайте.j*j