Як знайти кількість дільників цілого числа

Дільниками числа 24 є числа 1, 2, 3, 4, 6, 8, 12, 24, тобто у числа 24 є 8 дільників. Ця стаття розповість вам, як швидко знайти кількість дільників цілого числа.

Кроки

1. 1 Наприклад, знайдемо кількість дільників числа 24. Спочатку розкладемо це число: 24 = 2 * 3
2. 2 Зверніть увагу на показники ступенів. Вони рівні 3 і 1 (якщо у ступеня показника немає, то показник дорівнює 1).
3. 3 Додайте одиницю до кожного показника ступеня і перемножте отримані значення: (3 + 1) * (1 + 1) = 4 * 2 = 8. Кількість дільників числа 24 дорівнює 8.

Математика 6 клас – Н.А. Тарасенкова

Подивіться на малюнок 1. Ви бачите, що б яблук поділили на 2 купки по З яблука в кожній. Тут число б є діленим, число 2 — дільником, а число З — часткою. Але в яблук можна поділити і по-іншому — розкласти їх на 3 купки по 2 яблука в кожній. Тоді для діленого б число 3 є дільником, а число 2 — часткою. Це означає, що числа 2 і 3 є дільниками числа б. Водночас число б є кратним для кожного зі своїх дільників — і для числа 2, і для числа 3. Дільники і кратні є натуральними числами.

Дільником числа називається таке число, на яке ділиться дане число.

Кратним числа називається таке число, яке ділиться надане число.

? Чи є інші дільники в числа б? Так. Число б ділиться ще на 1 і саме на себе. Отже, загалом у числа 6 є чотири дільники:

кожне натуральне число, починаючи з числа 2, має принаймні два дільники — число 1 і саме це число. Інші дільники шукають за спеціальними правилами.

Задача. Знайдіть усі дільники числа: 1) 7; 2) 12; 3) 25.

1) У числа 7 є принаймні два дільники — 1 і 7. На жодне інше натуральне число 7 не ділиться, тому в нього лише два дільники: 1 і 7.

2) Число 12 має принаймні два дільники — 1 і 12. Далі послідовно перевіряємо подільність числа 12 на натуральні числа від 2 до 11.12 : 2 = б, тому 2 і 6 — дільники числа 12. 12:3 = 4, тому 3 і 4 — теж дільники числа 12. На 5, 7, 8, 9, 10 і 11 число 12 не ділиться. Отже, дільниками числа 12 е числа: 1; 2; 3;4; 6; 12.

3) У числа 25 є принаймі два дільники: 1 25. На 2, 3 і 4, а також на числа від 6 до 24 це число не ділиться. 25 : 5 = 5, тому число 5 є дільником числа 25, при чому двічі. Але рівні дільники враховують лише один раз. Отже, у числа 25 не чотири, а три дільники: 1; 5; 25.

Натуральне число, яке має лише два дільники (1 і саме число), називається простим.

Натуральне число, яке має більше двох дільників, називається складеним.

Наприклад, 7 — просте число, а 12 і 25 — складені.

? Чи є 1 простим числом? А складеним? Ні, оскільки в числа 1 тільки один дільник. Отже, число 1 особливе. Вено і не просте, і не складене.

найменшим простим числом є число 2.

Щоб виписати деяку кількість простих чисел, можна скористатися способом, який придумав ще в III ст. до н. е. Ератосфен Кіренський (276 р. до н. е. — 194 р. до н. е.), грецький математик, астроном, географ і поет. На честь ученого цей спосіб носить назву «решето Ератосфена». На малюнку (с. 4) ви бачите, як знаходили прості числа від 2 до 50. Спробуйте самостійно пояснити, як це робили.

1. Яке число називається дільником числа?

2. Яке число називається кратним числа?

3. На які два числа завжди ділиться будь-яке натуральне число більше за 1?

4. Яке натуральне число називається простим? Наведіть приклад.

5. Назвіть найменше просте число.

6. Яке натуральне число називається складеним? Наведіть приклад.

1′. Чи кожне натуральне число має дільники?

2′. Чи правильно, що число 3 є дільником числа:

3′. Чи правильно, що число 12 є кратним числа:

4′. Назвіть: 1) три прості числа; 2) три складені числа.

1) простим числом; 2) складеним числом?

6°. Дано числа: 3; 4; 6; 8; 9. Випишіть ті з них, які є дільниками числа: 1)8; 2) 12; 3) 16; 4) 18.

7°. Дано числа: 2; 3; 5; 6; 8. Випишіть ті з них, які є дільниками числа: 1)9; 2) 15; 3) 32; 4) 40.

8°. Знайдіть усі дільники числа: 1) 8; 2) 14; 3) 28; 4) 39.

9°. Знайдіть усі дільники числа: 1) 9; 2) 11; 3) 25; 4) 36.

10°. Дано числа: 10; 12; 14; 16; 18; 20. Випишіть ті з них, які є кратними числа: 1) 4; 2) 6; 3) 3; 4) 8.

11°. Дано числа: 14; 18; 21; 24; 28; 30. Випишіть ті з них, які є кратними числа: 1) 6; 2) 7; 3) 10; 4) 3.

12°. Дід Мороз приніс дітям у дитячий садок подарунки і подарував кожній дитині однакову їх кількість. Скільки подарунків отримала кожна дитина, якщо в садочку 64 дитини, а подарунків було:

1)256; 2) 320; 3)448?

13°. На координатному промені позначте точку А(2) та ще чотири точки з координатами, кратними координаті точки А.

14°. На координатному промені позначте точку В(3) та ще три точки з координатами, кратними координаті точки В.

15°. Дано числа: 10; 11; 13; 15; 18; 23. Випишіть ті з них, які є:

1) простими; 2) складеними.

16°. Дано числа: 21; 25; 27; 29; 32; 37. Випишіть ті з них, які є:

1) простими; 2) складеними.

17°. Дано числа: 7; 8; 10; 13; 19; 24; 31; 34; 37; 39; 42; 43. Оберіть серед них ті, які мають:

1) тільки два дільники; 2) більше двох дільників.

18. Скільки дільників має число:

1) 125; 2) 216; 3) 256; 4) 400?

19. Знайдіть усі дільники числа:

1) 96; 2) 100; 3) 144; 4) 180.

20. Знайдіть усі дільники числа:

1) 84; 2) 72; 3) 125; 4) 120.

21. У магазині кольорові олівці продають у коробках по 16 олівців у кожній. Чи зможе вчитель малювання купити:

1) 48 олівців; 2) 64 олівці; 3) 96 олівців; 4) 120 олівців?

Якщо так, то скільки коробок?

22. У спортивних змаганнях беруть участь 108 школярів. Чи можна поділити їх на команди:

1) по 6 осіб; 2) по 12 осіб; 3) по 16 осіб; 4) по 24 особи?

Якщо так, то скільки буде таких команд?

23. Знайдіть усі двоцифрові числа, які є кратними числа:

24. Знайдіть усі двоцифрові числа, які є кратними числа:

25. Знайдіть усі трицифрові числа, менші від 400, для яких число 35 є дільником.

26. Знайдіть чотири найменші числа, дільниками яких є числа 6 і 8.

27. Чи можна записати просте число у вигляді:

1) суми двох парних чисел;

2) суми двох непарних чисел;

3) суми парного і непарного числа?

Відповідь поясніть. Наведіть приклади.

28*. Знайдіть будь-які чотири натуральні числа, які мають рівно три дільники. Яку закономірність ви помітили?

29*. Знайдіть будь-які чотири натуральні числа, які мають рівно чотири дільники. Яку закономірність ви помітили?

30*. Запишіть число 48 у вигляді різниці квадратів двох простих чисел, менших від 25.

31. Оксанка купувала в магазині цукерки й отримала 2 грн 25 к. здачі. Чи могла вона отримати здачу тільки монетами: 1) по 5 к.; 2) по 10 к.; 3) по 25 к.; 4) по 50 к.? Якщо так, то скільки було монет?

32. Вік Іринки, її старшої сестри Ольги, їхніх мами та бабусі — усе це є дільниками числа 165. Знайдіть вік сестри, мами та бабусі дівчинки, якщо відомо, що Іринці — 11 років.

ЗАДАЧІ НА ПОВТОРЕННЯ

34. Магазин за перший день продав 180 кг помідорів, а за другий — 270 кг. На скільки відсотків більше магазин продав помідорів за другий день?

Використовуючи сайт ви погоджуєтесь з правилами користування

Віртуальна читальня освітніх матеріалів для студентів, вчителів, учнів та батьків.

Наш сайт не претендує на авторство розміщених матеріалів. Ми тільки конвертуємо у зручний формат матеріали з мережі Інтернет які знаходяться у відкритому доступі та надіслані нашими відвідувачами.

Якщо ви являєтесь володарем авторського права на будь-який розміщений у нас матеріал і маєте намір видалити його зверніться для узгодження до адміністратора сайту.

Ми приєднуємось до закону про авторське право в цифрову епоху DMCA прийнятим за основу взаємовідносин в площині вирішення питань авторських прав в мережі Інтернет. Тому підтримуємо загальновживаний механізм “повідомлення-видалення” для об’єктів авторського права і завжди йдемо на зустріч правовласникам.

Копіюючи матеріали во повинні узгодити можливість їх використання з авторами. Наш сайт не несе відподвідальність за копіювання матеріалів нашими користувачами.

Кількість простих дільників числа. Скільки дільників має просте число?

Кожен школяр знає, що всі числа діляться на прості і складові. Більше того, тим, хто ретельно вивчає математику, відомі і їх властивості. Однак якщо відповідь на питання, скільки дільників має просте число, прихований у самому визначенні цього поняття, то з’ясувати кількість простих дільників для заданого — досить складна задача. Вона вирішується із застосуванням методу перебору і імовірнісних алгоритмів, реалізованих на ЕОМ.

Достовірно відомо, що серйозним вивченням властивостей простих чисел першими стали займатися стародавні греки. Однак про їх існування було відомо за кілька тисячоліть до того, як Аристотель включив теореми про їх властивості в свої знамениті “Початку”. Стародавні греки придумали і решето Ератосфена, що представляє собою алгоритм знаходження простих чисел з проміжку [1,n].

У 17 столітті прорив у вивченні зробили П’єр Ферма і Марен Мерсенн. Перший сформулював теорему, згодом названу його ім’ям, згідно з якою всі числа виду 22n — прості, довівши її для n =1..4. Однак згодом Леонардом Ейлером було показано, що при n=5 виходить складене число. Паралельно з цим Марен Мерсенн виділив прості числа виду 2p – 1, в яких p – просте. Вони цікаві тим, що для них легко перевірити відповідність критерію простоти. Враховуючи цей факт, числа Мерсенна використовують для виявлення надвеликих простих чисел. На даний момент граничне з відомих виглядає як 277232917 ? 1 .

Крім того, їх широко використовують при створенні генераторів випадкових чисел, що мають широке застосування на практиці.

Велику роль у дослідженні простих чисел зіграли також Лежандра і Гаусс. Ці вчені висунули гіпотезу про їх щільності.

Якщо можна відразу ж назвати прості дільники числа 4, то для великих чисел зробити це зазвичай досить важко. Про рішення цієї проблеми люди стали замислюватися ще кілька тисячоліть тому. Зокрема, старогрецький математик Ератосфен, який жив на межі третього і другого століть до Різдва Христового придумав алгоритм знаходження всіх простих чисел, менших цілого числа n.

Він отримав назву решета, так як «просіює» або по-сучасному «фільтрує» всі числа, крім простих.

Алгоритм складається з наступних команд: виписати всі цілі числа від 2 до n; присвоїти змінній значення p 2, так як це найменше просте число; закреслити в списку всі числа від 2p до n, кратні p; присвоїти значення змінної p значення першого, не закресленого числа записаної послідовності, яка більше p; повторювати 3-й і 4-й, поки можливо.

Якщо все зроблено правильно, то у списку залишаться не закресленими всі прості числа від двох до n.

Для реалізації решета Ератосфена на електронно-обчислювальній машині використовують модернізований алгоритм. На 3-му кроці можна закреслювати числа, починаючи з числа p2, так як всі складові числа, які менші нього, до цього часу вже будуть закреслені. Тоді зупинка роботи алгоритму повинна відбутися, коли виконається умова p2>n.

Слід також врахувати, що всі прості числа, за винятком двійки, — непарні, тому, починаючи з p2 можна «фільтрувати» за 2p.

Основна теорема арифметики

Згідно з визначенням, просте число має два дільника. Один з них — 1, а другий — сама ця величина.

Перш ніж з’ясувати, яка кількість простих дільників числа, варто приділити трохи часу вивченню основної теореми арифметики. Згідно їй, натуральне число n > 1 можна уявити, як n = p1*. ?*pk, де p1, . , pm — прості числа. При цьому таке подання є єдиним з точністю до порядку слідування його співмножників.

Наслідок цієї теореми можна сформулювати наступним чином: будь-яке натуральне число n представимо у вигляді n = p1 d1*p2d2 * . * pkdm (в іншому формулюванні: канонічне розкладання числа n на прості множники має вигляд n = p1 d1*p2d2*? . *pkdm), де p1

Крім того, вже відому вам основна теорема арифметики можна перефразувати наступним чином: будь-канонічне розкладання n можна вважати тотожними, якщо не звертати уваги на порядок дільників. Це означає, що на практиці для значної частини чисел існує безліч досить простих алгоритмів їх розкладання на прості множники, які в результаті дають один і той же результат. Критерій простоти

Перш ніж з’ясувати, як можна знайти найбільший простий дільник числа (НПД) n, слід розібратися з іншим важливим питанням.

Отже, з’ясуємо, за яким алгоритмом можна встановити, чи є у величини інші дільники крім одиниці і його самого.

Зробити це можна шляхом перебору простих чисел p1, . pk. Причому завершити цикл можна, як тільки pi+1, для якого проводилася перевірка, буде задовольняти умові (pi+1)2> n.

Дамо пояснення, чому перебір можна обмежити pi>=sqr(n).

Припустимо, у числа n, досліджуваного на простоту є деякий дільник p. Тоді d=n/p так само буде його дільником. Але, так як d і p — різні числа, жоден з них не може бути більше кореня n.

Як знайти найбільший простий дільник числа n

Знайти НПД n, можна, діючи за такою схемою: Поділити n на два, якщо воно парне або на три, якщо непарне. Виняток становить n, остання цифра десяткового запису якого нуль або п’ять. Таке число можна відразу розділити на п’ять. Якщо результат не ціле число, то ділять n на наступні цілі числа, перебираючи їх аж до pi>=sqr(n).

Над отриманим числом n1 виробляють всі дії в тому ж порядку, що представлений вище, тільки з умовою pi>=sqr(n1).

Якщо ж ні на одному з кроків перебору n1 не ділиться на одне з простих чисел, то n ціле і є своїм же НПД. В іншому випадку отримуємо n2 і продовжуємо ділення з перебором до моменту, коли на (i+1) кроці встановимо, що ni — ціле. Приклад

Знайдемо прості дільники числа 276. ділимо на “два”; отримуємо 138; так як число парне, то знову ділимо на “два”; результат — 69; ділимо на наступне просте число “три”; отримуємо 23.

Так як це число просте, можемо підвести підсумок. Простими дільниками 276 є 2, 3 і 23. Як знайти кількість простих дільників числа

Якщо мова йде про цілу малому числі, то рішення такої задачі не представляє ніякої складності. Розглянемо конкретний приклад. Знайдемо прості дільники числа 54.

Для цього: 54 ділимо на “два” і отримуємо 27; 27 непарна, тому розділимо його вже не на “два”, а на наступне просте число, тобто “три”; зауважимо, що 27=33; таким чином, розкладання 54 має вигляд 54 = 21 * 33, тобто прості дільники числа 54 — це “два” і “три”.

Однак це не все, що ми хотіли знати. Тепер знайдемо кількість простих дільників числа 54. Воно дорівнює добутку ступенів простих множників канонічного розкладання числа n = p1*d1 p2d2*? . *pmdm, збільшених на 1. Іншими словами, в загальному випадку K = (d1+1)*. * (dm+1).

Тоді для 54 маємо До = 2 * 4 = 8, тобто загальне число дільників дорівнює восьми.

Зверніть увагу, що все значно спростилося, якщо б мова йшла про 23, 37, 103 та ін, так як кожен знає, скільки дільників у простого числа.

Знайти кількість простих дільників числа 9990. так як число 9990 закінчується на цифру “нуль”, то воно ділиться на п’ять і на два. маємо 999. в результаті розподілу на три маємо 333; знову ділимо на три, отримуємо 111; ділимо на три, маємо 37; 37 просте число, так як не ділиться без остачі на жодне з простих чисел, що знаходяться між двійкою і коренем з числа 37; підраховуємо кількість простих дільників числа 9990. Це 2,3,5 і 37, тобто всього їх чотири. Проблема великих чисел

Як не дивно, задача знаходження всіх простих множників числа є досить складною. Справа в тому, що досі ми розглядали лише числа, десятковий запис яких складалася з одного-чотирьох знаків. Для них всі обчислення виконуються в кілька кроків і їх цілком можна осилити, маючи під рукою лише ручку і аркуш паперу. По-іншому обстоїть справа, коли йдеться про, наприклад, 1000-значний числі. Щоб знайти всі його прості множники буде потрібно більше мільярда років, якщо навіть буде задіяний найпотужніший суперкомп’ютер у світі. Прості числа і захист інформації

Кожна сучасна людина, що користується можливостями, які виникли завдяки появі локальних комп’ютерних мереж та Інтернету, потребує захисту конфіденційності своїх особистих даних, електронного листування тощо З цією метою використовуються криптографічні алгоритми з відкритим ключем.

У системах з десятками і сотнями користувачів керування ключами є серйозною проблемою. Щоб запобігти оволодіння зловмисником ключовою інформацією, необхідно введення в процес шифрування якоїсь випадкової величини.

Для цієї мети найбільш поширені на даний момент алгоритми RSA використовують великі прості числа.

Існує всього 10151 простих чисел довжиною 1 – 512 бітів включно. У той же час для чисел, які близькі до n, ймовірність того факту, що випадково обране число буде простим — 1/ln n. Таким чином, повна кількість простих чисел, менших n дорівнює n/ln n. Це дозволяє вважати, що вкрай малоймовірно, що 2 людини виберуть одне і те ж велике просте число.

Тест Міллера — Рабіна

У криптографічних метою часто використовують саме цей вид визначення простоти числа, який має кілька модифікацій.

Тест Міллера—Рабіна заснований на перевірці ряду умов, виконуваних для чисел, які діляться тільки на 1 і на самих себе. Якщо хоча б одна з вимог порушено, це «экзаменуемое» число визнається складовим.

Для даного m знаходяться цілі непарне число t і s, такі щоб виконувалася умова m-1=2st.

Наслідком теорема Рабіна є той факт, що якщо r чисел, які вибрані випадково, визнані свідками для визначення простоти числа m, то ймовірність того, що воно складене, не може перевершувати (4-r).

Тепер ви знаєте, скільки дільників має просте число і як з’ясувати найбільш примітивний алгоритм обчислення НПД. Ці знання допоможуть вам у вирішенні багатьох практичних завдань.