Как можно ускорить алгоритм?

Question

[vseminelybim]

Собственно говоря, есть вот такой банальный и простой алгоритм, который вроде как решает задачу, но не умещается по времени. Есть ли варианты как-то ускорить это безобразие? И скрин задачки для понимания что вообще происходит. Буду очень благодарен, если подкинете вариантов:)

#include <iostream>

using namespace std;

int main() {

    long int K;
    long int L = 0;

    cin >> K;

    for (long int i = 2; i < K; i++)
    {
        if (K % (i + 1) == 0) {
            L = i;
            break;
        }
    }
    cout << L;

    return 0;
}

Answer 1

[Wataru]

Вы правильно поняли, что вам надо найти минимальный делитель числа K.

Проблема в том, что если число K простое - то вы будете проходиться до него. Есть трюк - достаточно проверять только числа до корня из K. Ведь если у числа есть какой-то минимальный собственный (меньше него самого) делитель, то он точно меньше корня (потому что делителей как минимум два, и если минимальный из них больше корня, то их произведение - больше самого числа).

Если вы не нашли делителя до корня, то число простое и в качестве делитеял можно брать все K и тогда ответ будет K-1.

Comments

[Alexandroppolus]

можно ещё в 2 раза ускорить - проверять только нечетные делители, увеличивая i на 2

[Wataru]

Alexandroppolus, можно, но это уже экономия на спичках будет. После ускорения в 10000 раз - эти 2 раза уже вряд ли понадобятся.

Answer 2

[mayton2019]

Какое-то время я посвятил играм с простыми числами. В студенчестве еще.
Вот тут не надо каждый раз прибавлять единичку.
if (K % (i + 1) == 0) {
Ее просто надо учесть в условиях цикла.
if (K % i == 0) {
Далее. Если нужно найти первый попавшийся делитель - то не надо перебирать все числа. Достаточно только 2 и все нечетные. Или даже лучше задать хард-кодом таблицу простых чисел до 2^16. Это как раз будет половина разрядной сетки int32.
int primes[] = { 2,3,5,7,11,13,17...... 65521 }
Это даст хорошее ускорение для поиска. Хотя время загрузки executable может увеличится. Кстати у меня много вопросов к бенчмаркам где стоит запредельно короткое время инициализации (0.25 s). Здесь - практически невозможно вычленить где время занимает алгоритм а где - просто запуск процесса операционки. Обычно когда меряют что-то подобное - меряют длительные процессы хотя-бы порядка минут но никак не секунд.

Comments

[Wataru]

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

[mayton2019]

Wataru, это неважно. И это не отменяет моего вопроса. Где здесь доля времени чистого алгоритма и где - техническое обслуживание процесса ОС.

Answer 3

[vanyamba-electronics]

Первый игрок назначает например число три (K). Второй назначает число 2 (L=K-1), и всегда забирает последнюю пуговицу. Что-то явно не то с условиями задачи.