Назад Зміст Вперед

Задачі на знаходження дільників натуральних чисел

Число i є дільником натурального числа n, якщо n % i==0.

У кожного натурального числа n обов’язково є два дільники: 1 та n.

Всі інші дільники натурального числа n (якщо вони є), знаходяться в інтервалі [2, n/2].

Натуральне число називається простим, якщо у нього немає дільників в інтервалі [2, n/2].

Щоб знайти всі дільники числа n, потрібно перевірити всі числа i з інтервалу [1, n] на умову n % i==0. Тобто це буде такий цикл:

for (i=1;i<=n;i++) if (n % i==0)...

Щоб перевірити, чи є число n простим, достатньо перевірити на цю умову всі числа з інтервалу [2, n/2]. Тобто це буде такий цикл:

for (i=2;i<=n/2;i++) if (n % i==0)...

Приклад 1

Дано натуральне число n. Знайти всі його дільники, їх кількість та суму.

Дано: натуральне число n.

Знайти: Надрукувати його дільники, підрахувати їх кількість та знайти їх суму.

Результати роботи програми

Змінні:

Вхідні:

• n – натуральне число (цілого типу)

Вихідні:

• i – дільники та параметр циклу (цілого типу)
• k – кількість дільників (цілого типу)
• s – сума дільників (цілого типу).

Алгоритм

1. Спочатку вводимо натуральне число n.
2. Ми будемо знаходити кількість та суму. Тому присвоїмо початкове значення 0 змінним k та s.
3. Нам потрібно знайти всі дільники числа n. Вони знаходяться в інтервалі [1, n].
4. У циклі for (i=1;i<=n;i++) будемо знаходити ці дільники. Для кожного i будемо перевіряти умову n % i==0 и, якщо вона вірна (тобто i є дільником n), то
   1. Виводимо на екран цей дільник.
   2. Підраховуємо цей дільник оператором k++.
   3. Накопичуємо цей дільник у суму оператором s=s+i
5. Коли цикл закінчиться, виводимо знайдені значення кількості та суми на екран.

Програма

#include <iostream>
using namespace std;

int main()
{
    int n, i, k, s;
    k=s=0; // Ініціалізація змінних k та s
    cin >> n;
    for (i=1; i<=n; i++)
    {
        if (n % i==0) // Перевірка, чи i є дільником n
        {
            cout << i << " ";
            k++; s=s+i; // Збільшення k та додавання i до s
        }
    }
    cout << "\nк=" << k << " с=" << s;
    return 0;
}

Приклад 2

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

Дано: два натуральних числа A та B.

Знайти: Для кожного з чисел A, A+1, A+2,...,B знайти всі дільники, підрахувати їх кількість та знайти їх суму.

Результати роботи програми

Змінні:

Вхідні:

• A – ліва границя інтервалу (цілого типу)
• B – права границя інтервалу (цілого типу)

Вихідні:

• n – натуральне число з інтервалу [A,B] та параметр зовнішнього циклу (цілого типу)
• i – дільники числа n та параметр внутрішнього циклу (цілого типу)
• k – кількість дільників числа n (цілого типу)
• s – сума дільників числа n (цілого типу).

Алгоритм

1. Спочатку вводимо натуральні числа A та B, що є границями інтервалу.
2. Для кожного числа n з цього інтервалу ми повинні повністю виконати попередній алгоритм, починаючи з пункту 2. Тому у нас будуть вкладені цикли:
   1. зовнішній цикл: for (n=a;n<=b;n++)
      1. перебирає числа n з інтервалу [A,B]
      2. виводить ці числа на екран
      3. для кожного числа n встановлює початкове значення для кількості та суми дільників s=0;k=0. Це обов’язково потрібно зробити у зовнішньому циклі, але перед внутрішнім.
   2. внутрішній цикл for (i=1;i<=n;i++) if (n % i==0) для кожного числа n знаходить дільники та:
      1. Виводить на екран цей дільник.
      2. Підраховує цей дільник оператором k++.
      3. Накопичує цей дільник у суму оператором s=s+i
   3. Коли внутрішній цикл закінчиться, виводимо знайдені значення кількості та суми для даного числа n на екран та переходимо на наступний виток зовнішнього циклу для обробки наступного числа.

Програма

#include <iostream>
using namespace std;

int main()
{
    int a, b, n, i, k, s;
    cin >> a >> b;
    for (n=a; n<=b; n++) // Цикл по числам від a до b
    {
        cout << "n=" << n << ": ";
        s=k=0; // Ініціалізація s і k для кожного n
        for (i=1; i<=n; i++) // Перевірка дільників числа n
        {
            if (n % i==0) // Якщо i є дільником n
            {
                cout << i << " ";
                k++; s=s+i; // Збільшення кількості дільників і суми
            }
        }
        cout << "\nк=" << k << " с=" << s << "\n";
    }
    return 0;
}

Приклад 3

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

Знайти: Для кожного з чисел 300, 301, 302,...,400 додати всі парні дільники, і, якщо сума буде кратна 10, то вивести на екран число та знайдену суму.

Результати роботи програми

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

Змінні:

Вхідних даних немає.

Вихідні:

• n – натуральне число з інтервалу [300,400] та параметр зовнішнього циклу (цілого типу)
• i – дільники числа n та параметр внутрішнього циклу (цілого типу)
• s – сума дільників числа n (цілого типу).

Алгоритм

1. Так же як і у попередньому прикладі, у нас будуть вкладені цикли:
   1. зовнішній цикл: for (n=300;n<=400;n++)
      1. перебирає числа n з інтервалу [300,400]
      2. для кожного числа n встановлює початкове значення для суми дільників s=0.
      3. внутрішній цикл for (i=1;i<=n;i++) if (n % i==0 && i % 2==0) для кожного числа n знаходить суму парних дільників s=s+i
   2. Коли внутрішній цикл закінчиться, перевіряємо знайдену суму s і, якщо вона кратна 10 (s % 10==0), то виводимо на екран число n, знайдену суму та переходимо на наступний виток зовнішнього циклу для обробки наступного числа.

Програма

#include <iostream>
using namespace std;

int main()
{
    int n, i, s;
    // Зовнішній цикл: перебираємо числа n від 300 до 399
    for (n=300; n<400; n++)
    {
        s=0; // Ініціалізація суми парних дільників
        // Внутрішній цикл: перебираємо можливі дільники i від 1 до n
        for (i=1; i<=n; i++)
        {
            // Якщо i є парним дільником n
            if (n % i==0 && i % 2==0)
            {
                s=s+i; // Додаємо i до суми
            }
        }
        // Якщо сума не дорівнює 0 і кратна 10
        if (s!=0 && s % 10==0)
        {
            // Виводимо n та суму s
            cout << " n=" << n << " s=" << s << "\n";
        }
    }
    return 0;
}

Приклад 4

Дано натуральне число n. Чи воно просте?

Дано: натуральне число n.

Знайти: З’ясувати, чи є у числа дільники у інтервалі [2, n / 2].

Результати роботи програми

Змінні:

Вхідні:

• n – натуральне число (цілого типу)

Вихідні:

• p – ознака наявності дільників (логічного типу, p=true немає дільників - число просте, p=false є дільники )

Проміжні:

• i – дільники та параметр циклу (цілого типу)

Алгоритм

1. Спочатку вводимо натуральне число n.
2. Ми будемо використовувати алгоритм з ознакою. Тому присвоїмо початкове значення ознаці p=true. Тобто вважаємо, що дільників немає, тобто число просте.
3. Тепер у циклі for (i=2;i<=n / 2; i++) будемо шукати дільники. Для кожного i будемо перевіряти умову n % i==0 и, якщо вона вірна (тобто i є дільником n), то установимо значення ознаки p=false.
4. Коли цикл закінчиться, то перевіримо значення ознаки:
   1. Якщо p=true, то дільників немає, число просте, відповідь 'yes'.
   2. Якщо p=false, то є дільники, число не просте, відповідь 'no'.

Програма

#include <iostream>
using namespace std;

int main()
{
    int n, i; bool p=true;
    cin >> n;
    for (i=2; i<=n/2; i++)
    {
        if (n % i==0) // Перевірка, чи є i дільником n
        {
            p=false; // Якщо є дільник, змінюємо p на false
        }
    }
    if (p) // Якщо p залишилася true, число просте
    {
        cout << "yes ";
    }
    else // Якщо p стала false, число складене
    {
        cout << "no";
    }
    return 0;
}

Приклад 5

Знайдіть в інтервалі [A,B] всі прості числа

Дано: два натуральних числа A та B.

Знайти: Для кожного з чисел A, A+1, A+2,...,B з’ясувати, чиє воно простим. Якщо число просте, то вивести його на екран.

Результати роботи програми

Змінні:

Вхідні:

• A – ліва границя інтервалу (цілого типу)
• B – права границя інтервалу (цілого типу)

Вихідні:

• p – ознака наявності дільників (логічного типу, p=true немає дільників, p=false є дільники )

Проміжні:

• n – натуральне число з інтервалу [A,B] та параметр зовнішнього циклу (цілого типу)
• i – дільники числа n та параметр внутрішнього циклу (цілого типу)

Алгоритм

1. Спочатку вводимо натуральні числа A та B, що є границями інтервалу.
2. Для кожного числа n з цього інтервалу ми повинні повністю виконати попередній алгоритм, починаючи з пункту 2. Тому у нас будуть вкладені цикли:
   1. зовнішній цикл: for (n=a; n<=b; n++)
      1. перебирає числа n з інтервалу [A,B]
      2. присвоює початкове значення ознаці p=true. Тобто вважаємо, що дільників у числа n немає. Це обов’язково потрібно зробити у зовнішньому циклі, але перед внутрішнім.
   2. У внутрішньому циклі for (i=2; i<=n / 2; i++) будемо шукати дільники числа n. Для кожного i будемо перевіряти умову n % i==0 и, якщо вона вірна (тобто i є дільником n), то установимо значення ознаки p=false.
   3. Коли внутрішній цикл закінчиться, то перевіримо значення ознаки:
      1. якщо p=true, то дільників немає, число n просте і тому виводиться на екран, а потім виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.
      2. якщо p=false, то є дільники, число не просте, число не виводиться, виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.

   Програма

   #include <iostream>
   using namespace std;
   
   int main()
   {
       int a, b, n, i; bool p;
       cin >> a >> b;
       for (n=a; n<=b; n++)
       {
           p=true; // Ініціалізація p як true для кожного n
           for (i=2; i<=n/2; i++)
           {
               if (n % i==0) // Перевірка, чи є i дільником n
               {
                   p=false; // Якщо є дільник, змінюємо p на false
               }
           }
           if (p) // Якщо p залишилася true, виводимо просте число
           {
               cout << n << " ";
           }
       }
       return 0;
   }
   

   Варіанти задач

   Варіант 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. Послідовність чисел Фібоначчі f₁, f₂, ...f_n утворюється за законом f₁=1; f₂=1; f_i=f_i-1+f_i-2 (і= 3, 4 ...n). Дано натуральне число n. З n чисел послідовності Фібоначчі надрукувати тільки прості числа.

   Назад Зміст Вперед