C++ • Цикли з параметром

Тема 4 • Дільники натуральних чисел

Ділиться
без остачі?

Знаходимо дільники й розпізнаємо прості числа

12 : 3 = 4, остача 0

12 % 3 == 0

Отже, 3 є дільником 12

12 : 5 = 2, остача 2. Число 5 не є дільником 12.

Що потрібно пам’ятати

  • Тут натуральні числа починаються з 1. Розглядаємо лише додатні дільники.
  • Усі дільники n лежать від 1 до n включно. Наприклад, у 12 це 1, 2, 3, 4, 6, 12.
  • Для n > 1 числа 1 та n є двома різними дільниками. Для n = 1 це один і той самий дільник.
  • Не кожне перевірене i є дільником. Дільником воно стає лише за умови n % i == 0.

Приклади використовують звичайний перебір без масивів і функцій. Для навчальних запусків задавайте 1 ≤ n ≤ 100000, а для інтервалів 1 ≤ A ≤ B ≤ 1000. Сума в перших двох програмах має тип long long, який зберігає більші цілі числа, ніж int.

Приклад 1. Дільники одного числа

Дано натуральне число n. Виведіть усі його додатні дільники, їхню кількість і суму. Перебираємо i від 1 до n включно. Якщо остача від ділення n на i дорівнює нулю, друкуємо i, збільшуємо лічильник і додаємо i до суми.

Для перевірки ділення використовуємо n % i == 0. Починаємо з 1: на нуль ділити не можна.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count = 0;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
            count++;
            sum = sum + i;
        }
    }
    cout << "\nКількість: " << count;
    cout << "\nСума: " << sum << "\n";
    return 0;
}

Приклад вводу: 12

Результат:

1 2 3 4 6 12 
Кількість: 6
Сума: 28

Приклад 2. Дільники кожного числа з інтервалу

Дано натуральні числа A та B, A ≤ B. Для кожного числа з цього інтервалу знайдіть усі дільники, їхню кількість і суму.

Зовнішній цикл вибирає число n, внутрішній перевіряє можливі дільники i. Перед внутрішнім циклом щоразу створюємо count = 0 та sum = 0. Інакше до результату наступного числа потраплять дані попереднього.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int n = a; n <= b; n++) {
        int count = 0;
        long long sum = 0;
        cout << n << ": ";
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                cout << i << " ";
                count++;
                sum = sum + i;
            }
        }
        cout << "| кількість: " << count << ", сума: " << sum << "\n";
    }
    return 0;
}

Приклад вводу: 10 14

Результат:

10: 1 2 5 10 | кількість: 4, сума: 18
11: 1 11 | кількість: 2, сума: 12
12: 1 2 3 4 6 12 | кількість: 6, сума: 28
13: 1 13 | кількість: 2, сума: 14
14: 1 2 7 14 | кількість: 4, сума: 24

Приклад 3. Сума парних дільників

Для чисел від 300 до 400 включно знайдіть суму парних дільників. Виведіть число та суму, якщо сума додатна й кратна 10.

Уточнення до початкової умови: у непарних чисел немає парних дільників, тому сума дорівнює 0. Нуль також кратний 10. Тут, як у початковому коді сторінки, відбираємо лише додатні суми. Якщо за умовою потрібно врахувати й нуль, залиште тільки sum % 10 == 0.

Перебираємо лише парні i: 2, 4, 6… Число 400 також перевіряємо, тому в зовнішньому циклі записано n <= 400.

#include <iostream>
using namespace std;

int main() {
    for (int n = 300; n <= 400; n++) {
        int sum = 0;
        for (int i = 2; i <= n; i = i + 2) {
            if (n % i == 0) {
                sum = sum + i;
            }
        }
        if (sum > 0 && sum % 10 == 0) {
            cout << n << " " << sum << "\n";
        }
    }
    return 0;
}

Результат:

304 600
316 480
336 960
342 520
348 720
354 480
356 540
358 360
368 720
378 640
380 720
398 400
400 930

Приклад 4. Чи є число простим

Просте число має рівно два різні додатні дільники: 1 і саме число. Числа 2, 3, 5, 7 прості. Число 1 має лише один дільник, тому не є ані простим, ані складеним.

Для початку використаємо простий спосіб: перевіримо i від 2 до n / 2 включно. Якщо знайдемо хоча б один дільник, число не є простим. Інших дільників між n / 2 та n у натурального числа немає.

Запис bool prime = (n >= 2); означає: для n ≥ 2 ознака спочатку дорівнює true, а для 1 дорівнює false. Знайдений дільник змінює ознаку лише на false.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool prime = (n >= 2);
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            prime = false;
        }
    }
    if (prime) {
        cout << "Число просте\n";
    } else {
        cout << "Число не є простим\n";
    }
    return 0;
}

Приклад вводу: 17

Результат:

Число просте

Приклад 5. Прості числа з інтервалу

Для кожного натурального числа з інтервалу [A, B] перевіряємо, чи є воно простим. Ознаку prime задаємо заново для кожного n. Завдяки перевірці n ≥ 2 число 1 не потрапить у відповідь.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int n = a; n <= b; n++) {
        bool prime = (n >= 2);
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                prime = false;
            }
        }
        if (prime) {
            cout << n << " ";
        }
    }
    cout << "\n";
    return 0;
}

Приклад вводу: 10 14

Результат:

11 13 

Подивись на кожну перевірку

Число від 1 до 60. У першому режимі знаходимо всі дільники. У другому перевіряємо простоту за алгоритмом прикладу 4.

Додатково: дільники утворюють пари

У числа 36 маємо пари 1 · 36, 2 · 18, 3 · 12, 4 · 9 і 6 · 6. У кожній парі хоча б один множник не більший за √36 = 6.

Тому для перевірки простоти достатньо перевіряти i від 2, поки i · i ≤ n. Це не означає, що всі дільники лежать до √n: наприклад, 18 є дільником 36.

Для навчальних значень n до 100000 у прикладах 4 та 5 можна замінити заголовок внутрішнього циклу таким:

for (int i = 2; i * i <= n; i++)

Решта перевірки не змінюється. Спочатку розбери зрозумілий спосіб до n / 2, а потім порівняй кількість перевірок. Для 97 у першому способі перевіряємо 2…48, а у другому лише 2…9. Межу зі знаком ≤ зберігаємо: інакше можна пропустити квадрат простого числа, наприклад 49.

Варіанти для самостійної роботи

Нумерацію, числові межі та два пункти кожного варіанта збережено. Для змінних меж інтервалів вважайте, що 1 ≤ A ≤ B та 1 ≤ N ≤ M.

Якщо парних дільників немає, їхня кількість і сума дорівнюють 0, а середнє арифметичне не визначене. У такому разі виведіть повідомлення. Дружні числа мають бути різними; кожну пару виводьте один раз. У варіанті 9 за однакової мінімальної суми можна вивести найменше з відповідних чисел. У варіанті 17 для типу long long обмежте n значеннями від 1 до 92.

Варіант 1

  1. Дано натуральне число n. Вивести на екран всі його парні дільники.
  2. Знайдіть кількість простих чотиризначних чисел.
↑ До вибору варіанта

Варіант 2

  1. Дано натуральне число n. Знайти суму його непарних дільників.
  2. Надрукуйте всі цілі числа з інтервалу від 1 до 300 які мають 5 дільників.
↑ До вибору варіанта

Варіант 3

  1. Дано натуральне число n. Знайти кількість його парних дільників.
  2. Дано натуральне число n. Надрукуйте стільки символів «+», скільки дільників у цього числа. Наприклад, якщо n=4, то на екрані потрібно надрукувати: +++
↑ До вибору варіанта

Варіант 4

  1. Для кожного цілого числа з інтервалу [10,15] знайдіть всі непарні дільники.
  2. Складіть програму для графічного зображення подільності чисел від 1 до n (значення n введіть з клавіатури). У кожному рядку друкуйте чергове число і стільки символів «+», скільки дільників у цього числа. Наприклад, якщо n=4, то на екрані має бути надруковано:

    1+
    2++
    3++
    4+++

↑ До вибору варіанта

Варіант 5

  1. Дано натуральне число n. Надрукуйте всі його дільники та знайдіть середнє арифметичне його парних дільників.
  2. Надрукуйте всі цілі числа з інтервалу від 300 до 400, у яких сума дільників кратна 10.
↑ До вибору варіанта

Варіант 6

  1. Знайдіть кількість простих чотиризначних чисел.
  2. Для кожного цілого числа з інтервалу [130;140] знайдіть всі непарні дільники та їх кількість.
↑ До вибору варіанта

Варіант 7

  1. Надрукуйте всі тризначні паліндроми , що є простими числами.
  2. Знайдіть суму цілих чисел з інтервалу від 1 до 200, у яких 6 дільників.
↑ До вибору варіанта

Варіант 8

  1. В інтервалі [A,B] знайдіть кількість простих чисел.
  2. Знайдіть суму непарних дільників кожного з цілих чисел від 50 до 60.
↑ До вибору варіанта

Варіант 9

  1. Для кожного цілого числа з інтервалу [30,36] знайдіть кількість його парних дільників.
  2. Знайдіть число в інтервалі [A,B] у якого сума дільників мінімальна.
↑ До вибору варіанта

Варіант 10

  1. Для кожного цілого числа з інтервалу [15,20] знайдіть всі його непарні дільники.
  2. Знайдіть кількість п’ятизначних паліндромів, що є простими числами.
↑ До вибору варіанта

Варіант 11

  1. В інтервалі [50,70] знайдіть числа у яких сума непарних дільників є непарною.
  2. Знайдіть прості дільники кожного цілого числа з інтервалу [A,B].
↑ До вибору варіанта

Варіант 12

  1. Для кожного цілого числа з інтервалу [16,24] знайдіть середнє арифметичне його парних дільників.
  2. Два натуральних числа називаються дружніми, якщо кожне з них дорівнює сумі всіх дільників іншого (виключаючи саме число). Знайдіть всі пари натуральних дружніх чисел, що менші за 10000.
↑ До вибору варіанта

Варіант 13

  1. Для кожного цілого числа з інтервалу [120;130] знайдіть всі парні дільники та їх суму.
  2. Натуральне число називається досконалим, якщо воно дорівнює сумі своїх дільників, включаючи 1 та не враховуючи саме число. Наприклад, число 6 досконале (6=1+2+3). Знайдіть всі досконалі числа, що менші за 10000.
↑ До вибору варіанта

Варіант 14

  1. Дано натуральні числа А, В та С. В інтервалі [A,B] знайдіть числа які мають С дільників.
  2. Два простих числа, різниця між якими дорівнює числу 2, називаються «близнюками». Складіть програму пошуку та друку всіх «близнюків», що належать інтервалу [N,M].
↑ До вибору варіанта

Варіант 15

  1. Для кожного цілого числа з інтервалу [A,B] знайдіть всі його дільники, що кратні 3.
  2. Складіть програму для перевірки, чи можна задане натуральне число подати у вигляді добутку двох простих чисел.
↑ До вибору варіанта

Варіант 16

  1. З інтервалу [15,25] виведіть на екран числа, у яких 4 дільники.
  2. Складіть програму для перевірки, чи можна задане натуральне число подати у вигляді квадрата простого числа.
↑ До вибору варіанта

Варіант 17

  1. Знайдіть натуральне число з інтервалу від A до B яке має максимальну кількість дільників. Якщо таких чисел декілька, то знайдіть мінімальне з них.
  2. Послідовність чисел Фібоначчі f1, f2, ...fn утворюється за законом f1=1; f2=1; fi=fi-1+fi-2 (і= 3, 4 ...n). Дано натуральне число n. З n чисел послідовності Фібоначчі надрукувати тільки прості числа.
↑ До вибору варіанта