Варіант 1
- Дано натуральне число n. Вивести на екран всі його парні дільники.
- Знайдіть кількість простих чотиризначних чисел.
Тема 4 • Дільники натуральних чисел
Знаходимо дільники й розпізнаємо прості числа
12 : 3 = 4, остача 0
12 % 3 == 0Отже, 3 є дільником 12
12 : 5 = 2, остача 2. Число 5 не є дільником 12.
Приклади використовують звичайний перебір без масивів і функцій. Для навчальних запусків задавайте 1 ≤ n ≤ 100000, а для інтервалів 1 ≤ A ≤ B ≤ 1000. Сума в перших двох програмах має тип long long, який зберігає більші цілі числа, ніж int.
Дано натуральне число 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
Дано натуральні числа 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
Для чисел від 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
Просте число має рівно два різні додатні дільники: 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
Результат:
Число просте
Для кожного натурального числа з інтервалу [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+
2++
3++
4+++