Задание 25

В этих задачах необходимо перебрать диапазон чисел и выбрать из него нужные вам.

Самое важное что нужно понимать в этих задачах - это то, что при поиске делителей числа $n$ можно не перебирать все числа от $[2; n-1]$. Достаточно перебрать числа от $[2; \sqrt{n}]$. Если $n$ делится на какое-то $k$, меньшее $\sqrt{n}$, тогда оно делится ещё и на $n/k$. Так, перебирая числа только от $2$ до $\sqrt{n}$, мы можем на каждом шаге цикла получать сразу два делителя. Это сильно сэкономит время.

Скорее всего, ваша задача решится и полным перебором, но всё же следует знать, как оптимизировать эту программу

Такие задачи Python выполняет ощутимо медленнее, поэтому придётся подождать, пока выведется первое значение.

Пример 1

Задача

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Java

public class Example1 {
    public static void main(String[] args) {
        // перебираем числа заданного диапазона
        for (int i = 174457; i <= 174505; i++) {
            // кол-во делителей равно 0
            int dCnt = 0;
            // создаём массив для сохранения двух делителей
            int[] dArr = new int[2];
            // перебираем числа от [2;i-1]
            for (int d = 2; d < i; d++) {
                // если d - делитель i
                if (i % d == 0) {
                    // если найденных делителей меньше двух
                    if (dCnt < 2)
                        // сохраняем его в соответствующий элемент массива
                        dArr[dCnt] = d;
                    // увеличиваем кол-во делителей на 1
                    dCnt++;
                }
            }
            // если у числа ровно два делителя
            if (dCnt == 2) {
                // выводим их
                System.out.println(dArr[0] + " " + dArr[1]);
            }
        }
    }
}

C++

#include <iostream>

// главный метод программы
int main() {
    // перебираем числа заданного диапазона
    for (int i = 174457; i <= 174505; i++) {
        // кол-во делителей равно 0
        int dCnt = 0;
        // создаём массив для сохранения двух делителей
        int dArr[2];
        // перебираем числа от [2;i-1]
        for (int d = 2; d < i; d++) {
            // если d - делитель i
            if (i % d == 0) {
                // если найденных делителей меньше двух
                if (dCnt < 2)
                    // сохраняем его в соответствующий элемент массива
                    dArr[dCnt] = d;
                // увеличиваем кол-во делителей на 1
                dCnt++;
            }
        }
        // если у числа ровно два делителя
        if (dCnt == 2) {
            // выводим их
            std::cout << dArr[0] << " " << dArr[1] << std::endl;
        }
    }
    return 0;
}

Python

# перебираем числа заданного диапазона
for i in range(174457, 174505 + 1):
    # создаём список для сохранения делителей
    ds = list()
    # перебираем числа от [2;i-1]
    for d in range(2, i):
        # если d - делитель i
        if i % d == 0:
            ds.append(d)

    # если у числа ровно два делителя
    if len(ds) == 2:
        # выводим их
        print(ds)

Вывод программы:

3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251

Можно было бы программно отсортировать эти данные, но проще сделать это вручную. Т.к. делители мы перебирали от меньшего к большему, то в каждой строке делители уже идут по возрастанию.

Получается, нам нужно просто отсортировать строки по первому числу

Ответ:

2 87251
3 58153
5 34897
7 24923
13 13421
59 2957
149 1171
211 827

Пример 2

Задача

Среди чисел, больших 520000, найти такие, сумма всех делителей которых, не считая единицы и самого числа, образует число-палиндром (например, число 1221: если его «перевернуть», получается то же самое число). Вывести первые пять чисел, удовлетворяющих вышеописанному условию, справа от каждого числа вывести его максимальный делитель.

В этой задаче подразумевается, что простые числа, имеющие сумму делителей 0, не подходят. Будьте внимательны на ЕГЭ и уточняйте такие моменты.

Java

public class Example2 {
    public static void main(String[] args) {
        // кол-во найденных чисел изначально равно 0
        int cnt = 0;
        // перебираем числа от 520000 до очень большого, я просто умножил на 10 исходное
        // если не хватит, просто увеличьте верхнюю границу перебора
        for (int i = 520000; i <= 5200000; i++) {
            // сумма делителей
            int sum = 0;
            // максимальный делитель
            int maxD = 1;
            // перебираем числа от [2;i-1]
            for (int d = 2; d < i; d++) {
                // если d - делитель i
                if (i % d == 0) {
                    // прибавляем делитель к сумме
                    sum += d;
                    // т.к. мы перебираем делители в порядке возрастания,
                    // то последний сохранённый будет максимальным
                    maxD = d;
                }
            }
            // если число простое
            if (sum == 0)
                // переходим к следующему шагу цикла
                continue;

            // формируем строку из числа
            String s = sum + "";
            // переменная, отвечающая на вопрос, является ли строка палиндромом
            boolean p = true;
            // перебираем все элементы строки до середины, если их нечётное число, то
            // центральный элемент уже не перебираетс
            for (int j = 0; j < s.length() / 2; j++) {
                // если перебираемый элемент и зеркальный ему во второй половине строки
                // не совпадают
                if (s.charAt(j) != s.charAt(s.length() - 1 - j)) {
                    // строка не может быть палиндромом
                    p = false;
                    // завершаем перебор символов строки
                    break;
                }
            }
            // если строка - палиндром
            if (p) {
                // выводим число, выводим
                System.out.println(i + " " + maxD);
                // увеличиваем кол-во найденных чисел на 1
                cnt++;
                // если найдено пять и больше
                if (cnt >= 5)
                    // завершаем цикл
                    break;
            }
        }
    }
}

C++

#include <iostream>

// главный метод программы
int main() {
    // кол-во найденных чисел изначально равно 0
    int cnt = 0;
    // перебираем числа от 520000 до очень большого, я просто умножил на 10 исходное
    // если не хватит, просто увеличьте верхнюю границу перебора
    for (int i = 520000; i <= 5200000; i++) {
        // сумма делителей
        int sum = 0;
        // максимальный делитель
        int maxD = 1;
        // перебираем числа от [2;i-1]
        for (int d = 2; d < i; d++) {
            // если d - делитель i
            if (i % d == 0) {
                // прибавляем делитель к сумме
                sum += d;
                // т.к. мы перебираем делители в порядке возрастания,
                // то последний сохранённый будет максимальным
                maxD = d;
            }
        }
        // если число простое
        if (sum == 0)
            // переходим к следующему шагу цикла
            continue;

        // создаём строку с двоичным представлением перебираемого значения
        char l[17];
        // отправляем в буфер p строковое представление числа с заданным основанием
        itoa(sum, l, 10);
        // создаём строку на основе буффера
        std::string s(l);
        // переменная, отвечающая на вопрос, является ли строка палиндромом
        bool p = true;
        // перебираем все элементы строки до середины, если их нечётное число, то
        // центральный элемент уже не перебираетс
        for (int j = 0; j < s.length() / 2; j++) {
            // если перебираемый элемент и зеркальный ему во второй половине строки
            // не совпадают
            if (s[j] != s[s.length() - 1 - j]) {
                // строка не может быть палиндромом
                p = false;
                // завершаем перебор символов строки
                break;
            }
        }
        // если строка - палиндром
        if (p) {
            // выводим число, выводим
            std::cout << i << " " << maxD <<std::endl;
            // увеличиваем кол-во найденных чисел на 1
            cnt++;
            // если найдено пять и больше
            if (cnt >= 5)
                // завершаем цикл
                break;
        }
    }
    return 0;
}

Python

# кол-во найденных чисел изначально равно 0
cnt = 0

# перебираем числа от 520000 до очень большого, я просто умножил на 10 исходное
# если не хватит, просто увеличьте верхнюю границу перебора
for i in range(520000, 5200000):
    # сумма делителей
    sum = 0
    # максимальный делитель
    maxD = 1
    # перебираем числа от [2;i-1]
    for d in range(2, i):
        # если d - делитель i
        if i % d == 0:
            # прибавляем делитель к сумме
            sum = sum + d
            # т.к. мы перебираем делители в порядке возрастания,
            # то последний сохранённый будет максимальным
            maxD = d

    # если число простое
    if sum == 0:
        # переходим к следующему шагу цикла
        continue

    # формируем строку из числа
    s = str(sum)
    # переменная, отвечающая на вопрос, является ли строка палиндромом
    p = True
    # перебираем все элементы строки до середины, если их нечётное число, то
    # центральный элемент уже не перебираетс
    for j in range(len(s) // 2):
        # если перебираемый элемент и зеркальный ему во второй половине строки
        # не совпадают
        if s[j] != s[len(s) - 1 - j]:
            # строка не может быть палиндромом
            p = False
            # завершаем перебор символов строки
            break

    # если строка - палиндром
    if p:
        # выводим число, выводим
        print(i, maxD)
        # увеличиваем кол-во найденных чисел на 1
        cnt = cnt + 1
        # если найдено пять и больше
        if cnt >= 5:
            # завершаем цикл
            break

Вывод программы:

520211 16781
520993 47363
521653 47423
521947 16837
522077 22699

Ответ:

520211 16781
520993 47363
521653 47423
521947 16837
522077 22699

Пример 3

Задача

Найдите 5 составных (не простых) чисел больших 800000, таких, что сумма их наименьшего и наибольшего нетривиальных делителей (не считая единицы и самого числа) делится на 138. В качестве ответа приведите 5 наименьших чисел, соответствующих условию. Формат вывода: для каждого из найденных чисел в отдельной строке запишите само число, а затем сумму его наименьшего и наибольшего нетривиальных делителей.

Хотя эту задачу можно решить почти так же, как предыдущую. Чтобы показать, как быстро проверить число на простоту, в этой задаче напишем отдельный метод для этой проверки.

Java

public class Example3 {
    // Проверка числа a на простоту, возвращает true, если число простое
    // false - если нет
    static boolean isPrime(int a) {
        // перебираем все числа от 2 до корня
        for (int i = 2; i < Math.sqrt(a) + 1; i++) {
            // если a делится на i
            if (a % i == 0)
                // число составное
                return false;
        }
        // если не нашли ни одного делителя, число - простое
        return true;
    }

    public static void main(String[] args) {
        // кол-во найденных чисел изначально равно 0
        int cnt = 0;
        // перебираем числа от 800000 до очень большого, я просто умножил на 10 исходное
        // если не хватит, просто увеличьте верхнюю границу перебора
        for (int i = 800000; i <= 8000000; i++) {
            // если число простое
            if (isPrime(i))
                // переходим к следующему шагу цикла
                continue;

            // минимальный делитель, изначально равен -1
            int minD = -1;
            // максимальный делитель
            int maxD = 1;
            // перебираем числа от [2;i-1]
            for (int d = 2; d < i; d++) {
                // если d - делитель i
                if (i % d == 0) {
                    // если не найдено ни одного делителя
                    if(minD==-1)
                        // сохраняем первый(минимальный) делитель
                        minD = d;

                    // т.к. мы перебираем делители в порядке возрастания,
                    // то последний сохранённый будет максимальным
                    maxD = d;
                }
            }

            // если строка - палиндром
            if ((minD+maxD)%138==0) {
                // выводим число, выводим
                System.out.println(i + " " + (minD+maxD));
                // увеличиваем кол-во найденных чисел на 1
                cnt++;
                // если найдено пять и больше
                if (cnt >= 5)
                    // завершаем цикл
                    break;
            }
        }
    }
}

C++

#include <iostream>
#include <cmath>

// Проверка числа a на простоту, возвращает true, если число простое
// false - если нет
bool isPrime(int a) {
    // перебираем все числа от 2 до корня
    for (int i = 2; i < std::sqrt(a) + 1; i++) {
        // если a делится на i
        if (a % i == 0)
            // число составное
            return false;
    }
    // если не нашли ни одного делителя, число - простое
    return true;
}

// главный метод программы
int main() {
    // кол-во найденных чисел изначально равно 0
    int cnt = 0;
    // перебираем числа от 800000 до очень большого, я просто умножил на 10 исходное
    // если не хватит, просто увеличьте верхнюю границу перебора
    for (int i = 800000; i <= 8000000; i++) {
        // если число простое
        if (isPrime(i))
            // переходим к следующему шагу цикла
            continue;

        // минимальный делитель, изначально равен -1
        int minD = -1;
        // максимальный делитель
        int maxD = 1;
        // перебираем числа от [2;i-1]
        for (int d = 2; d < i; d++) {
            // если d - делитель i
            if (i % d == 0) {
                // если не найдено ни одного делителя
                if (minD == -1)
                    // сохраняем первый(минимальный) делитель
                    minD = d;

                // т.к. мы перебираем делители в порядке возрастания,
                // то последний сохранённый будет максимальным
                maxD = d;
            }
        }

        // если строка - палиндром
        if ((minD + maxD) % 138 == 0) {
            // выводим число, выводим
            std::cout << i << " " << minD + maxD << std::endl;
            // увеличиваем кол-во найденных чисел на 1
            cnt++;
            // если найдено пять и больше
            if (cnt >= 5)
                // завершаем цикл
                break;
        }
    }
    return 0;
}

Python

# Проверка числа a на простоту, возвращает true, если число простое
from math import sqrt


# false - если нет
def isPrime(a):
    # перебираем все числа от 2 до корня
    for i in range(2, int(sqrt(a) + 1)):
        # если a делится на i
        if a % i == 0:
            # число составное
            return False

    # если не нашли ни одного делителя, число - простое
    return True


# кол-во найденных чисел изначально равно 0
cnt = 0

# перебираем числа от 800000 до очень большого, я просто умножил на 10 исходное
# если не хватит, просто увеличьте верхнюю границу перебора
for i in range(800000, 8000000):
    # если число простое
    if isPrime(i):
        # переходим к следующему шагу цикла
        continue

    # минимальный делитель, изначально равен -1
    minD = -1
    # максимальный делитель
    maxD = 1
    # перебираем числа от [2;i-1]
    for d in range(2, i):
        # если d - делитель i
        if i % d == 0:
            # если не найдено ни одного делителя
            if minD == -1:
                # сохраняем первый(минимальный) делитель
                minD = d

            # т.к. мы перебираем делители в порядке возрастания,
            # то последний сохранённый будет максимальным
            maxD = d

    # если строка - палиндром
    if (minD + maxD) % 138 == 0:
        # выводим число, выводим
        print(i, " ", (minD + maxD))
        # увеличиваем кол-во найденных чисел на 1
        cnt = cnt + 1
        # если найдено пять и больше
        if cnt >= 5:
            # завершаем цикл
            break

Вывод программы:

800120 400062
800253 266754
800273 21666
800375 160080
800396 400200

Ответ:

800120 400062
800253 266754
800273 21666
800375 160080
800396 400200

Задания для самостоятельного выполнения