Создайте программу src/1948.c, которая находит наи...

Ниже приведён пример реализации программы src/1948.c, которая ищет наибольший простой делитель введённого целого числа, не используя операторы деления (/) и взятия остатка от деления (%). Вместо этого применяется подход с повторным вычитанием или повторным сложением.

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

c
#include <stdio.h>

// Функция для вычисления абсолютного значения (без использования библиотечных функций).
int absolute_value(int x) {
    if (x < 0) {
        return -x;
    }
    return x;
}

// Функция для проверки, делится ли a на b без остатка, 
// используя только повторное сложение (аналог % и == 0, но без %).
// Предполагается, что a >= 0 и b > 0 при вызове из основного кода.
int is_divisible(int a, int b) {
    // Если b == 0, деление невозможно
    if (b == 0) {
        return 0;
    }
    int sum = 0;
    // Наращиваем sum, пока он не станет равен a или не превысит a
    while (sum < a) {
        sum += b; 
    }
    // Если sum ровно равен a, то a делится на b
    if (sum == a) {
        return 1;
    }
    return 0;
}

// Функция для целочисленного деления a на b (возвращает a / b),
// используя только повторное вычитание.
// Предполагается, что a >= 0 и b > 0.
int integer_division(int a, int b) {
    // Если b == 0, формально делить нельзя; для надёжности вернём 0
    if (b == 0) {
        return 0; 
    }
    int count = 0;
    int temp = a;
    while (temp >= b) {
        temp = temp - b;
        count++;
    }
    return count;
}

// Функция, проверяющая простоту числа x путём перебора делителей 
// (без % и /).
// Предполагается x >= 2 при вызове.
int is_prime(int x) {
    if (x < 2) {
        return 0;
    }
    // Перебираем все кандидаты от 2 до x-1
    // (в простом учебном решении без оптимизации до sqrt(x))
    for (int i = 2; i < x; i++) {
        if (is_divisible(x, i)) {
            return 0; // если x делится на i, то x не простое
        }
    }
    return 1;
}

// Функция, возвращающая наибольший простой делитель числа a.
// Если такого нет (или входные данные некорректны), возвращает -1.
int largest_prime_factor(int a) {
    // Если a == 0, 1 или -1, то простых делителей быть не может
    if (a == 0 || a == 1 || a == -1) {
        return -1;
    }

    // Работаем с модулем числа (наибольший простой делитель для отрицательного
    // возьмём таким же, как для положительного).
    int n = absolute_value(a);

    // Если после abs число стало 1, делителей простых нет.
    if (n == 1) {
        return -1;
    }

    int largestFactor = -1;

    // Перебираем все кандидаты i от 2 до n.
    // В худшем случае n может быть само простым.
    // При нахождении делителя i, будем делить n на i максимально.
    for (int i = 2; i <= n; i++) {
        // Проверяем, является ли i простым
        if (is_prime(i)) {
            // Пока n делится на i, делим n на i
            while (is_divisible(n, i)) {
                n = integer_division(n, i);
                largestFactor = i; // i - простой делитель
            }
            // Если n превратился в 1, дальнейший поиск не нужен
            if (n == 1) {
                break;
            }
        }
    }

    // Если так и не нашли делителя (largestFactor остался -1), это значит,
    // что исходное число само могло быть простым. Тогда простым делителем 
    // будет само число a (по модулю).
    // Но если всё-таки n > 1 после полного цикла, значит n — 
    // оставшийся простой делитель (больший, чем все i).
    if (largestFactor == -1) {
        // n > 1, т.е. n простое
        return n;
    } else if (n > 1) {
        // Если по какой-то причине после цикла осталось n > 1, оно само может быть фактором:
        // Однако если цикл закончился, а n > 1, то это число вероятно тоже простое.
        // Проверим это и примем решение, но обычно цикл учтёт и этот случай.
        if (is_prime(n) && n > largestFactor) {
            return n;
        }
    }

    return largestFactor;
}

int main(void) {
    int a;
    if (scanf("%d", &a) != 1) {
        // Ошибка чтения числа
        printf("n/a\n");
        return 0;
    }

    int result = largest_prime_factor(a);
    if (result == -1) {
        printf("n/a\n");
    } else {
        printf("%d\n", result);
    }

    return 0;
}

Пояснения к решению

1. absolute_value
   Простейшая функция, возвращающая модуль числа x.

2. is_divisible
   Для проверки, делится ли a на b, мы итерируемся, прибавляя b к sum, пока sum не станет равным a (тогда делится) или не превысит его (тогда не делится).

3. integer_division
   Вместо классического оператора деления используем повторное вычитание: пока «остаток» temp не стал меньше b, вычитаем b и накапливаем счётчик count. В итоге count есть целочисленный результат деления a / b.

4. is_prime
   Чтобы проверить, простое ли число x, перебираем все потенциальные делители от 2 до x - 1 и смотрим, делится ли x на них (через is_divisible). Если делится, значит не простое.

5. largest_prime_factor

   • Сразу обрабатываем некорректные случаи: 0, 1, -1.
   • Берём модуль числа, чтобы работать только с положительными значениями.
   • Перебираем кандидаты в делители i от 2 до n. Для каждого i:
     • Проверяем, прост ли он (is_prime(i)).
     • Пока n делится на i, делим его (через integer_division). Сам i запоминаем как потенциально наибольший простой делитель.
     • Если в какой-то момент n == 1, прерываем цикл.
   • Если после цикла так и не нашлось ни одного делителя (или же оказалось, что число само является простым), результатом может быть либо само число n (если оно > 1 и простое), либо -1 (ошибка / не найден делитель).

6. В main считываем число a. Если чтение прошло некорректно (не число) — выводим "n/a". Иначе вызываем largest_prime_factor(a). Если она возвращает -1, значит подходящего делителя нет или входные данные некорректны — печатаем "n/a", иначе выводим найденный делитель.

При запуске программа ждёт на вход целое число a и выводит наибольший простой делитель либо "n/a", если корректного делителя найти не удалось.