1

Суть задачи: нужно найти все числа в диапазоне start-end, которые возможно разложить на k простых множителей. Написанный код справляется со своей задачей, но это происходит за очень большое время. Собственно вопрос в том как можно сократить время выполнения задачи.

class Kata {
public static long[] countKprimes(int k, long start, long end) {

    ArrayList<Long> answer = new ArrayList<>();

    int count = 0;

    /*Собственно цикл который все это выполняет*/
    for (long i = start; i <= end; i++) {
        long temp = i;
        long mult = 2;

            while (count < k){
                if (temp % mult == 0) {count++; temp = temp / mult; continue;}
                if (mult > i || (mult > 2 && mult % 4 == 0)) break;
                else if(mult == 2) mult++;
                else mult += 2;
            }
            if (temp == 1 && count == k){answer.add(i);}
            count = 0;
        }

      /*Перенос полученной коллекции в массив*/
        long[] ans = new long[answer.size()];
        int m = 0;
        for(long i:answer) {ans[m] = i; m++;}
        return ans;
    }
}
13
  • 1
    интересно, за какое время оно делает свою работу? задание звучит как очень тяжелое для современных и неквантовых компьютеров
    – dgzargo
    6 фев 2018 в 18:04
  • @dgzargo например мой ноутбук такой поиск от 0 до 1000000 при k=5 выполняет за неизвестное кол-во времени(мне просто надоедает ждать), так что мне ваш сарказм не совсем понятен. В духе "не проверял, но осуждаю". 6 фев 2018 в 18:24
  • все намного хуже: проверял и осуждаю. я не разбирался в логике вашего метода, но думаю что там какой-то вид перебора. этот способ не может быть эффективным. посмотрите статью вики Факторизация целых чисел
    – dgzargo
    6 фев 2018 в 18:36
  • идея оптимизации в том чтоб хранить предыдущие подсчитанные значения в виде 4->2, 5->1, 8-> 4, и по ним находить более высокие разложения, например 5*2 =10, 2 множителя, 8*2. 16, 8 множителей. сокращённо посчитай степени двойки и комбинации из их сумм например 8 +4 = (4+2)*2
    – user184868
    6 фев 2018 в 18:46
  • может задачу можно упростить и не делать таких вычислений?
    – dgzargo
    6 фев 2018 в 18:52

4 ответа 4

1

Единицу отбрасываем, в виду нелепости ее использования в данной задаче. (я бы и 2 отбросил кстати)

Для начала вычисляем верхнюю границу допустимых для данных условий простых. Для этого берем k-1 простых, начиная с 2 и по очереди делим на них end

Double max = end;
for(int i=0; i<k-1; i++) max = max / getPrime(i);

Потом определяем нижнюю границу, для которой любые комбинации простых меньше нее не попадут в заданный диапазон

Long minPrime = (Long) Math.pow(start, 1.0 / k);

Потом находим все простые числа в диапазоне от 2 до maxPrime

Дальше перебираем все возможные комбинации из k этих простых, перемножаем и отбрасываем те, которые меньше start, либо больше end.

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

Примерный код работы с простыми

ArrayList<Long> primeNumbers = new ArrayList();

private Long getPrime(int index){
    while(primeNumbers.size() < index){
        primeNumbers.add(findNextPrime());
    }
    return primeNumbers[index];
}

private Long findNextPrime(){
  //  ищем нечетное число, больше максимального из primeNumbers,
  //  которое не делится ни на одно уже находящееся в этом массиве
}

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

1
if (temp % mult == 0) {count++; temp = temp / mult; mult = 2; continue;}

Зачем mult присваивать 2? Вы же все числа до mult уже перебрали.

if (mult > i || (mult > 2 && mult % 4 == 0)) break;

mult > i можно заменить на mult*mult > i. Если нет делителей до корня квадратного, то их и после не будет.

UPD: можно заменить даже не на mult* mult > i, а на mult*mult > temp. Это еще больше сократит кол-во итераций.

7
  • И еще, я бы сперва составил список всех простых от 2 до корня из end и перебирал бы их, а не все нечетные натуральные подряд. 6 фев 2018 в 19:51
  • Действительно, присваивание было излишним, но не потому что все числа были перебраны, а из-за continue которое не давало этой переменной увеличиваться при нахождении нужной пары число-делитель, а новый цикл for так и так ее возвращал на 2. Если проверять от 2 до корня из end то результат не верный, например если проверять от 0 до 100, то в случае с числом 46 выходит что: sqrt(100)=10; 46/2=23; и так как 23 простое число, но мы ограничены 10, то цикл просто не дойдет до нужного числа. 6 фев 2018 в 23:11
  • 1
    @АлександрКочуров, что мешает вам проверить остаток после цикла, и, если он не 1, добавить его как последний простой множитель?
    – vp_arth
    7 фев 2018 в 2:38
  • 1
    про корень и Ваш пример, если у числа нет простых делителей до корня из числа, то оно простое, В вашем случае это 23. Значит 23 - это и есть последний простой делитель. 7 фев 2018 в 6:52
  • 1
    Что за ересь вы тут пишете? А дальше на 2 кто делить будет? Дошли до корня, цикл закончился - тогда и проверяйте остаток
    – vp_arth
    7 фев 2018 в 13:06
0

Оптимизировать данное решение лучше всего сменой алгоритма :)

Мне в голову пришёл следующий вариант:

  • берём набор чисел от start до end, каждому назначаем число - счётчик найденных делителей (инициализируем нулём)
  • берём набор простых чисел от 2 до end
  • для каждого такого простого числа p:
    • перебираем степени m числа p от 1 до k+1:
      • для каждого тестируемого числа от start до end, которое делится на p^m, увеличиваем счётчик на 1
  • вернуть в качестве результата все числа от start до end, у которых счётчик оказался равным k

Вызов Вашей реализации countKPrimes(6, 34657, 49894) на моём компьютере отрабатывает 45 сек. Моя же реализация отрабатывает за долю секунды :)

Поскольку задача похожа на учебную, то полный код своего решения не привожу. Но дам подсказку, как оптимальнее обрабатывать числа, делящиеся на p^m.

Естественно, перебирать все числа от start до end неоптимально, нужно найти в диапазоне от start до end первое число, которое будет делиться на p^m, и затем от него идти по числам до end с шагом p^m.

Поскольку число p^m может быть достаточно велико, то поиск первого кратного ему числа простым перебором будет неоптимальным. Здесь тоже можно оптимизировать. Для этого возьмём остаток от деления start на p^m, и если остаток r не равен нулю, то увеличиваем число start на величину (p^m - r) - это и будет первое кратное p^m в тестируемом диапазоне.

2
  • Будет ли считать так же быстро если start - 0, end - 6000000(6 миллионов)? 11 фев 2018 в 10:32
  • У меня 7 сек. отрабатывает, включая генерацию простых чисел. Насколько это быстро или медленно, лучше познавать в сравнении с другими алгоритмами.
    – velial
    11 фев 2018 в 10:57
0

Не замудренное, читабельное, работающее быстрее чем мой изначальный код решение.

public class KPrimes {

public static long nPrime(long n) {
    int result = 0;
    for (long i = 2 ; i < Math.sqrt(n)+1 ; ++i) {
        while (n%i == 0) {
            result++;
            n /= i;
        }
    }
    if (n > 1) result++;
    return result;
}
public static long[] countKprimes(int k, long start, long end) {
    return LongStream.range(start,end+1).filter(x -> nPrime(x)==k).toArray();
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.