Задачі на знаходження дільників
натуральних чисел
Число i є дільником натурального числа n, якщо n mod i=0.
У кожного натурального числа n обов’язково є два дільники: 1 та n.
Всі інші дільники натурального числа n (якщо вини є), знаходяться в інтервалі [2, n div 2].
Натуральне число називається простим, якщо у нього немає дільників в інтервалі [2, n div 2].
Щоб знайти всі дільники числа n, потрібно перевірити всі числа i з інтервалу [1, n] на умову n mod i=0. Тобто це буде такий цикл:
for i:=1 to n do if n mod i=0 then...
Щоб перевірити, чи є число n простим, достатньо перевірити на цю умову всі числа з інтервалу [2, n div 2]. Тобто це буде такий цикл:
for i:=2 to n div 2 do if n mod i=0 then...
Приклад 1
Дано натуральне число n. Знайти всі його дільники, їх кількість та суму.
Дано: натуральне число n.
Знайти: Надрукувати його дільники, підрахувати їх кількість та знайти їх суму.
Результати роботи програми
| Ввід | Відповідь | Пояснення |
|---|---|---|
| 12 | 1 2 3 4 6 12 6 28 | Вводимо число 12. Його дільники: 1 2 3 4 6 12. Кількість дільників –6. Сума дільників – 28. |
Змінні:
Вхідні:
- n – натуральне число (цілого типу word, бо число натуральне)
Вихідні:
- i – дільники та параметр циклу (цілого типу word)
- k – кількість дільників (цілого типу word)
- s – сума дільників (цілого типу word).
Алгоритм
- Спочатку вводимо натуральне число n.
- Ми будемо знаходити кількість та суму. Тому присвоїмо початкове значення 0 змінним k та s.
- Нам потрібно знайти всі дільники числа n. Вони знаходяться в інтервалі [1, n].
- У циклі for i:=1 to n do будемо знаходити ці дільники. Для кожного i будемо перевіряти умову n mod i=0 і, якщо вона вірна (тобто i є дільником n), то
- виводимо на екран цей дільник оператором write(i,' ');
- підраховуємо цей дільник оператором k:=k+1;
- накопичуємо цей дільник у суму оператором s:=s+i.
- Коли цикл закінчиться, виводимо знайдені значення кількості та суми на екран оператором writeln(k,' ',s).
Програма
| var n,k,s,i:word; begin read(n); k:=0;s:=0; for i:=1 to n do if n mod i=0 then begin write(i,' '); k:=k+1; s:=s+i; end; writeln(k,' ',s); end. |
Приклад 2
Для кожного натурального числа з інтервалу [A, B] знайдіть всі дільники, їх кількість та суму.
Дано: два натуральних числа A та B.
Знайти: Для кожного з чисел A, A+1, A+2,..., B знайти всі дільники, підрахувати їх кількість та знайти їх суму.
Результати роботи програми
| Ввід | Відповідь | Пояснення |
|---|---|---|
| a=10 b=14 | дільники числа 10: 1 2 5 10 k=4 s=18 дільники числа 11: 1 11 k=2 s=12 дільники числа 12: 1 2 3 4 6 12 k=6 s=28 дільники числа 13: 1 13 k=2 s=14 дільники числа 14: 1 2 7 14 k=4 s=24 | Вводимо числа 10 та 14. Для кожного з чисел 10, 11, 12, 13, 14, знаходимо дільники, їх кількість та суму. Перед дільниками виводимо на екран і само число |
Змінні:
Вхідні:
- A – ліва границя інтервалу (цілого типу word, бо числа натуральні)
- B – права границя інтервалу (цілого типу word, бо числа натуральні)
Вихідні:
- n – натуральне число з інтервалу [A, B] та параметр зовнішнього циклу (цілого типу word, бо число натуральне)
- i – дільники числа n та параметр внутрішнього циклу (цілого типу word)
- k – кількість дільників числа n (цілого типу word)
- s – сума дільників числа n (цілого типу word).
Алгоритм
- Спочатку вводимо натуральні числа A та B, що є границями інтервалу.
- Для кожного числа n із цього інтервалу ми повинні повністю виконати попередній алгоритм, починаючи з пункту 2. Тому у нас будуть вкладені цикли:
- зовнішній цикл: for n:=a to b do
- перебирає числа n з інтервалу [A, B];
- виводить ці числа на екран write(n);
- для кожного числа n встановлює початкове значення для кількості та суми дільників s:=0; k:=0. Це обов’язково потрібно зробити у зовнішньому циклі, але перед внутрішнім.
- внутрішній цикл for i:=1 to n do if n mod i=0 then для кожного числа n знаходить дільники та:
- виводить на екран цей дільник оператором write(i,' ');
- підраховує цей дільник оператором k:=k+1;
- накопичує цей дільник у суму оператором s:=s+i.
- Коли внутрішній цикл закінчиться, виводимо знайдені значення кількості та суми для даного числа n на екран оператором writeln(k,' ',s) та переходимо на наступний виток зовнішнього циклу для обробки наступного числа.
- зовнішній цикл: for n:=a to b do
Блок–схема програми
Програма
| var a,b,n,i,k,s:word; begin write(a=');read(a); write('b=');read(b); for n:=a to b do begin write(дільники числа ',n,': '); s:=0;k:=0; for i:=1 to n do if n mod i=0 then begin write(i,' '); k:=k+1; s:=s+i; end; writeln(' k=',k,' s=',s); end; end. |
Приклад 3
Для кожного з чисел з інтервалу від 300 до 400 знайти суму дільників. Вивести на екран числа, у яких сума дільників кратна 10, а також саму суму дільників.
Знайти: Для кожного з чисел 300, 301, 302, ..., 400 додати всі дільники, і, якщо сума буде кратна 10, то вивести на екран число та знайдену суму.
Результати роботи програми
| Відповідь | Пояснення |
|---|---|
| n=304 s=620 n=312 s=840 n=316 s=560 n=319 s=360 n=323 s=360 n=327 s=440 n=328 s=630 n=342 s=780 n=343 s=400 n=344 s=660 n=348 s=840 n=349 s=350 n=351 s=560 n=354 s=720 n=356 s=630 n=358 s=540 n=359 s=360 n=360 s=1170 n=376 s=720 n=377 s=420 n=378 s=960 n=379 s=380 n=380 s=840 n=384 s=1020 n=389 s=390 n=395 s=480 n=398 s=600 n=399 s=640 | В програму нічого не вводиться. Числа у відповіді мають коментарі: спочатку виводиться число n, а потім сума його дільників s. |
Змінні:
Вхідних даних немає
Вихідні:
- n – натуральне число з інтервалу [300,400] та параметр зовнішнього циклу (цілого типу word, бо число натуральне)
- i – дільники числа n та параметр внутрішнього циклу (цілого типу word)
- s – сума дільників числа n (цілого типу word).
Алгоритм
- Так же як і у попередньому прикладі, у нас будуть вкладені цикли:
- зовнішній цикл: for n:=300 to 400 do
- перебирає числа n з інтервалу [300,400];
- для кожного числа n встановлює початкове значення для суми дільників s:=0;
- внутрішній цикл for i:=1 to n do if n mod i=0 then для кожного числа n знаходить суму дільників s:=s+i.
- Коли внутрішній цикл закінчиться, перевіряємо знайдену суму s і, якщо вона кратна 10 (s mod 10=0), то виводимо на екран число n та знайдену суму оператором write('n=',n,'s=',s) та переходимо на наступний виток зовнішнього циклу для обробки наступного числа.
- зовнішній цикл: for n:=300 to 400 do
Програма
| var n,i,s:word; begin for n:=300 to 400 do begin s:=0; for i:=1 to n do if n mod i=0 then s:=s+i; if s mod 10=0 then write(' n=',n,' s=',s); end; end. |
Приклад 4
Дано натуральне число n. Визначити, чи є воно простим?
Дано: натуральне число n.
Знайти: З’ясувати, чи є у числа дільники у інтервалі [2, n div 2].
Результати роботи програми
| Ввід | Відповідь | Пояснення |
|---|---|---|
| 12 | No | У числа 12 в інтервалі [2,6] є дільники: 2, 3, 4, 6. Тому число не є простим. |
| 17 | Yes | У числа 17 в інтервалі [2,8] немає дільників. Тому число є простим. |
Змінні:
Вхідні:
- n – натуральне число (цілого типу word, бо число натуральне)
Вихідні:
- p – ознака наявності дільників (логічного типу, p=false немає дільників, p=true є дільники )
Проміжні:
- i – дільники та параметр циклу (цілого типу word)
Алгоритм
- Спочатку вводимо натуральне число n.
- Ми будемо використовувати алгоритм з ознакою. Тому присвоїмо початкове значення ознаці p:=false. Тобто вважаємо, що дільників немає.
- Тепер у циклі for i:=2 to n div 2 do будемо шукати дільники. Для кожного i будемо перевіряти умову n mod i=0 і, якщо вона вірна (тобто i є дільником n), то установимо значення ознаки p:=true.
- Коли цикл закінчиться, то перевіримо значення ознаки:
- Якщо p=false, то дільників немає, число просте, відповідь 'yes'.
- Якщо p=true, то є дільники, число не просте, відповідь 'no'.
Програма
| var n,i: word; P:boolean; begin read(n);p:=false; for i:=2 to n div 2 do if n mod i=0 then p:=true; if not p then writeln('yes') else writeln('no'); end. |
Приклад 5
Знайдіть в інтервалі [A, B] всі прості числа.
Дано: два натуральних числа A та B.
Знайти: Для кожного з чисел A, A+1, A+2,..., B з’ясувати, чи є воно простим. Якщо число просте, то вивести його на екран.
Результати роботи програми
| Ввід | Відповідь | Пояснення |
|---|---|---|
| 10 14 | 11 13 | Вводимо числа 10 та 14. Для кожного з чисел 10, 11, 12, 13, 14, шукаємо дільники в інтервалі [2,n div 2]. У числа 10 в інтервалі [2,5] є дільники 2 та 5, тобто число не просте. У числа 11 в інтервалі [2,5] немає дільників, тобто число просте і тому виводиться на екран. У числа 12 в інтервалі [2,6] є дільники 2, 3, 4 та 6, тобто число не просте. У числа 13 в інтервалі [2,6] немає дільників, тобто число просте і тому виводиться на екран. У числа 14 в інтервалі [2,7] є дільники 2 та 7, тобто число не просте. |
Змінні:
Вхідні:
- A – ліва границя інтервалу (цілого типу word, бо числа натуральні)
- B – права границя інтервалу (цілого типу word, бо числа натуральні)
Вихідні:
- p – ознака наявності дільників (логічного типу, p=false немає дільників, p=true є дільники )
Проміжні:
- n – натуральне число з інтервалу [A, B] та параметр зовнішнього циклу (цілого типу word, бо число натуральне)
- i – дільники числа n та параметр внутрішнього циклу (цілого типу word)
Алгоритм
- Спочатку вводимо натуральні числа A та B, що є границями інтервалу.
- Для кожного числа n із цього інтервалу ми повинні повністю виконати попередній алгоритм, починаючи з пункту 2. Тому у нас будуть вкладені цикли:
- зовнішній цикл: for n:=a to b do
- перебирає числа n з інтервалу [A, B]
- присвоює початкове значення ознаці p:=false. Тобто вважаємо, що дільників у числа n немає. Це обов’язково потрібно зробити у зовнішньому циклі, але перед внутрішнім.
- У внутрішньому циклі for i:=2 to n div 2 do будемо шукати дільники числа n. Для кожного i будемо перевіряти умову n mod i=0 і, якщо вона вірна (тобто i є дільником n), то установимо значення ознаки p:=true.
- Коли внутрішній цикл закінчиться, то перевіримо значення ознаки:
- якщо p=false, то дільників немає, число n просте і тому виводиться на екран оператором write(n,' '), а потім виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.
- якщо p=true, то є дільники, число не просте, число не виводиться, виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.
- зовнішній цикл: for n:=a to b do
Програма
| var n,i,a,b: word; P:boolean; begin read(a,b); for n:=a to b do begin p:=false; for i:=2 to n div 2 do if n mod i=0 then p:=true; if not p then write(n,' '); end; end. |
Варіанти задач
- Дано натуральне число n. Вивести на екран всі його парні дільники.
- Дано натуральне число n. Знайти суму його непарних дільників.
- Дано натуральне число n. Знайти кількість його парних дільників.
- Для кожного цілого числа з інтервалу [10,15] знайдіть всі непарні дільники.
- Дано натуральне число n. Надрукуйте його дільники та знайдіть середнє арифметичне його парних дільників.
- Знайдіть всі прості трьохзначні числа.
- Надрукуйте всі трьохзначні паліндроми, що є простими числами.
- В інтервалі [A, B] знайдіть кількість простих чисел.
- Для кожного цілого числа з інтервалу [30, 36] знайдіть кількість його парних дільників.
- Для кожного цілого числа з інтервалу [15, 20] знайдіть суму його непарних дільників.
- Знайдіть суму непарних дільників для кожного з цілих чисел від 50 до 70.
- Для кожного цілого числа з інтервалу [16, 24] знайдіть середнє арифметичне його парних дільників.
- Для кожного цілого числа з інтервалу [120; 140] знайдіть всі непарні дільники та їх кількість.
- Для кожного цілого числа з інтервалу [A, B] знайдіть кількість його парних дільників.
- Для кожного цілого числа з інтервалу [A, B] знайдіть всі його дільники, що кратні 3.
- З інтервалу [15, 25] виведіть на екран числа, у яких 4 дільники.
Немає коментарів:
Дописати коментар