Сумма простых делителей числа

Сумма простых делителей числа

Дана последовательность из целых чисел. 0 — конец последовательности. Для каждого числа найти сумму его простых делителей. Оформить функцией определение суммы простых делителей числа.

Итак. Последовательность — массив. Заполняем его с клавиатуры и выводим как есть. Далее сами вычисления. Нужно найти простые числа до числа, для этого я буду использовать функцию isPrime (она на шарпе, но да я одну строчку изменил и работает на си), а нам еще нужно и делители. Значит остаток от деления числа должен быть равен нулю.

Для начало приведём экспериментальный материал (который был получен с помощью программы Derive (по формуле 1.(см.ниже)): для нахождения делителей числа «a», программа делила число «a» на другие числа не превосходящие само число и если остаток от деления был равен 0, то число записывалось как делитель «a». ):

Ниже приведены все делители чисел от 1 до 1000:

[12, [1, 2, 3, 4, 6, 12]]

[18, [1, 2, 3, 6, 9, 18]]

[20, [1, 2, 4, 5, 10, 20]]

[24, [1, 2, 3, 4, 6, 8, 12, 24]]

[28, [1, 2, 4, 7, 14, 28]]

[30, [1, 2, 3, 5, 6, 10, 15, 30]]

[32, [1, 2, 4, 8, 16, 32]]

[36, [1, 2, 3, 4, 6, 9, 12, 18, 36]]

[40, [1, 2, 4, 5, 8, 10, 20, 40]]

[42, [1, 2, 3, 6, 7, 14, 21, 42]]

[44, [1, 2, 4, 11, 22, 44]]

[45, [1, 3, 5, 9, 15, 45]]

[48, [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]]

[50, [1, 2, 5, 10, 25, 50]]

[52, [1, 2, 4, 13, 26, 52]]

[54, [1, 2, 3, 6, 9, 18, 27, 54]]

[56, [1, 2, 4, 7, 8, 14, 28, 56]]

[60, [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]]

[63, [1, 3, 7, 9, 21, 63]]

[64, [1, 2, 4, 8, 16, 32, 64]]

[66, [1, 2, 3, 6, 11, 22, 33, 66]]

[68, [1, 2, 4, 17, 34, 68]]

[70, [1, 2, 5, 7, 10, 14, 35, 70]]

[72, [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]]

[75, [1, 3, 5, 15, 25, 75]]

[76, [1, 2, 4, 19, 38, 76]]

[78, [1, 2, 3, 6, 13, 26, 39, 78]]

[80, [1, 2, 4, 5, 8, 10, 16, 20, 40, 80]]

[84, [1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]]

[88, [1, 2, 4, 8, 11, 22, 44, 88]]

[90, [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]]

[92, [1, 2, 4, 23, 46, 92]]

[96, [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96]]

[98, [1, 2, 7, 14, 49, 98]]

[99, [1, 3, 9, 11, 33, 99]]

[100, [1, 2, 4, 5, 10, 20, 25, 50, 100]]

[102, [1, 2, 3, 6, 17, 34, 51, 102]]

[104, [1, 2, 4, 8, 13, 26, 52, 104]]

[105, [1, 3, 5, 7, 15, 21, 35, 105]]

[108, [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108]]

[110, [1, 2, 5, 10, 11, 22, 55, 110]]

[112, [1, 2, 4, 7, 8, 14, 16, 28, 56, 112]]

[114, [1, 2, 3, 6, 19, 38, 57, 114]]

[116, [1, 2, 4, 29, 58, 116]]

[117, [1, 3, 9, 13, 39, 117]]

[120, [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]]

[124, [1, 2, 4, 31, 62, 124]]

[126, [1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126]]

[128, [1, 2, 4, 8, 16, 32, 64, 128]]

[130, [1, 2, 5, 10, 13, 26, 65, 130]]

[132, [1, 2, 3, 4, 6, 11, 12, 22, 33, 44, 66, 132]]

[135, [1, 3, 5, 9, 15, 27, 45, 135]]

[136, [1, 2, 4, 8, 17, 34, 68, 136]]

[138, [1, 2, 3, 6, 23, 46, 69, 138]]

[140, [1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140]]

[143, [1, 11, 13, 143]]

[144, [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144]]

[147, [1, 3, 7, 21, 49, 147]]

[148, [1, 2, 4, 37, 74, 148]]

[150, [1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]]

[152, [1, 2, 4, 8, 19, 38, 76, 152]]

[153, [1, 3, 9, 17, 51, 153]]

[154, [1, 2, 7, 11, 14, 22, 77, 154]]

[156, [1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156]]

[160, [1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 80, 160]]

[162, [1, 2, 3, 6, 9, 18, 27, 54, 81, 162]]

[164, [1, 2, 4, 41, 82, 164]]

[165, [1, 3, 5, 11, 15, 33, 55, 165]]

[168, [1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168]]

[170, [1, 2, 5, 10, 17, 34, 85, 170]]

[171, [1, 3, 9, 19, 57, 171]]

[172, [1, 2, 4, 43, 86, 172]]

[174, [1, 2, 3, 6, 29, 58, 87, 174]]

[175, [1, 5, 7, 25, 35, 175]]

[176, [1, 2, 4, 8, 11, 16, 22, 44, 88, 176]]

[180, [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]]

[182, [1, 2, 7, 13, 14, 26, 91, 182]]

[184, [1, 2, 4, 8, 23, 46, 92, 184]]

[186, [1, 2, 3, 6, 31, 62, 93, 186]]

[187, [1, 11, 17, 187]]

[188, [1, 2, 4, 47, 94, 188]]

[189, [1, 3, 7, 9, 21, 27, 63, 189]]

[190, [1, 2, 5, 10, 19, 38, 95, 190]]

[192, [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192]]

[195, [1, 3, 5, 13, 15, 39, 65, 195]]

[196, [1, 2, 4, 7, 14, 28, 49, 98, 196]]

[198, [1, 2, 3, 6, 9, 11, 18, 22, 33, 66, 99, 198]]

[200, [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 200]]

[202, [1, 2, 101, 202]]

[204, [1, 2, 3, 4, 6, 12, 17, 34, 51, 68, 102, 204]]

[206, [1, 2, 103, 206]]

Читайте также:  Сочетание клавиш для перезагрузки ноутбука

[207, [1, 3, 9, 23, 69, 207]]

[208, [1, 2, 4, 8, 13, 16, 26, 52, 104, 208]]

[209, [1, 11, 19, 209]]

[210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]]

[212, [1, 2, 4, 53, 106, 212]]

[214, [1, 2, 107, 214]]

[216, [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 27, 36, 54, 72, 108, 216]]

[218, [1, 2, 109, 218]]

[220, [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220]]

[221, [1, 13, 17, 221]]

[222, [1, 2, 3, 6, 37, 74, 111, 222]]

[224, [1, 2, 4, 7, 8, 14, 16, 28, 32, 56, 112, 224]]

[225, [1, 3, 5, 9, 15, 25, 45, 75, 225]]

[226, [1, 2, 113, 226]]

[228, [1, 2, 3, 4, 6, 12, 19, 38, 57, 76, 114, 228]]

[230, [1, 2, 5, 10, 23, 46, 115, 230]]

[231, [1, 3, 7, 11, 21, 33, 77, 231]]

[232, [1, 2, 4, 8, 29, 58, 116, 232]]

[234, [1, 2, 3, 6, 9, 13, 18, 26, 39, 78, 117, 234]]

[236, [1, 2, 4, 59, 118, 236]]

[238, [1, 2, 7, 14, 17, 34, 119, 238]]

[240, [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240]]

[242, [1, 2, 11, 22, 121, 242]]

[243, [1, 3, 9, 27, 81, 243]]

[244, [1, 2, 4, 61, 122, 244]]

[245, [1, 5, 7, 35, 49, 245]]

[246, [1, 2, 3, 6, 41, 82, 123, 246]]

[247, [1, 13, 19, 247]]

[248, [1, 2, 4, 8, 31, 62, 124, 248]]

[250, [1, 2, 5, 10, 25, 50, 125, 250]]

[252, [1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252]]

[253, [1, 11, 23, 253]]

[254, [1, 2, 127, 254]]

[255, [1, 3, 5, 15, 17, 51, 85, 255]]

[256, [1, 2, 4, 8, 16, 32, 64, 128, 256]]

[258, [1, 2, 3, 6, 43, 86, 129, 258]]

[260, [1, 2, 4, 5, 10, 13, 20, 26, 52, 65, 130, 260]]

[261, [1, 3, 9, 29, 87, 261]]

[262, [1, 2, 131, 262]]

[264, [1, 2, 3, 4, 6, 8, 11, 12, 22, 24, 33, 44, 66, 88, 132, 264]]

[266, [1, 2, 7, 14, 19, 38, 133, 266]]

[268, [1, 2, 4, 67, 134, 268]]

[270, [1, 2, 3, 5, 6, 9, 10, 15, 18, 27, 30, 45, 54, 90, 135, 270]]

[272, [1, 2, 4, 8, 16, 17, 34, 68, 136, 272]]

[273, [1, 3, 7, 13, 21, 39, 91, 273]]

[274, [1, 2, 137, 274]]

[275, [1, 5, 11, 25, 55, 275]]

[276, [1, 2, 3, 4, 6, 12, 23, 46, 69, 92, 138, 276]]

[278, [1, 2, 139, 278]]

[279, [1, 3, 9, 31, 93, 279]]

[280, [1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 35, 40, 56, 70, 140, 280]]

[282, [1, 2, 3, 6, 47, 94, 141, 282]]

[284, [1, 2, 4, 71, 142, 284]]

[285, [1, 3, 5, 15, 19, 57, 95, 285]]

[286, [1, 2, 11, 13, 22, 26, 143, 286]]

[288, [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 48, 72, 96, 144, 288]]

[290, [1, 2, 5, 10, 29, 58, 145, 290]]

[292, [1, 2, 4, 73, 146, 292]]

[294, [1, 2, 3, 6, 7, 14, 21, 42, 49, 98, 147, 294]]

[296, [1, 2, 4, 8, 37, 74, 148, 296]]

[297, [1, 3, 9, 11, 27, 33, 99, 297]]

[298, [1, 2, 149, 298]]

[299, [1, 13, 23, 299]]

[300, [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]]

[302, [1, 2, 151, 302]]

[303, [1, 3, 101, 303]]

[304, [1, 2, 4, 8, 16, 19, 38, 76, 152, 304]]

[306, [1, 2, 3, 6, 9, 17, 18, 34, 51, 102, 153, 306]]

[308, [1, 2, 4, 7, 11, 14, 22, 28, 44, 77, 154, 308]]

[309, [1, 3, 103, 309]]

[310, [1, 2, 5, 10, 31, 62, 155, 310]]

[312, [1, 2, 3, 4, 6, 8, 12, 13, 24, 26, 39, 52, 78, 104, 156, 312]]

[314, [1, 2, 157, 314]]

[315, [1, 3, 5, 7, 9, 15, 21, 35, 45, 63, 105, 315]]

[316, [1, 2, 4, 79, 158, 316]]

[318, [1, 2, 3, 6, 53, 106, 159, 318]]

[319, [1, 11, 29, 319]]

[320, [1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 160, 320]]

[321, [1, 3, 107, 321]]

[322, [1, 2, 7, 14, 23, 46, 161, 322]]

[323, [1, 17, 19, 323]]

[324, [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 324]]

[325, [1, 5, 13, 25, 65, 325]]

[326, [1, 2, 163, 326]]

[327, [1, 3, 109, 327]]

[328, [1, 2, 4, 8, 41, 82, 164, 328]]

[330, [1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330]]

[332, [1, 2, 4, 83, 166, 332]]

[333, [1, 3, 9, 37, 111, 333]]

[334, [1, 2, 167, 334]]

[336, [1, 2, 3, 4, 6, 7, 8, 12, 14, 16, 21, 24, 28, 42, 48, 56, 84, 112, 168, 336]]

[338, [1, 2, 13, 26, 169, 338]]

[339, [1, 3, 113, 339]]

[340, [1, 2, 4, 5, 10, 17, 20, 34, 68, 85, 170, 340]]

[341, [1, 11, 31, 341]]

[342, [1, 2, 3, 6, 9, 18, 19, 38, 57, 114, 171, 342]]

[344, [1, 2, 4, 8, 43, 86, 172, 344]]

[345, [1, 3, 5, 15, 23, 69, 115, 345]]

[346, [1, 2, 173, 346]]

[348, [1, 2, 3, 4, 6, 12, 29, 58, 87, 116, 174, 348]]

[350, [1, 2, 5, 7, 10, 14, 25, 35, 50, 70, 175, 350]]

[351, [1, 3, 9, 13, 27, 39, 117, 351]]

[352, [1, 2, 4, 8, 11, 16, 22, 32, 44, 88, 176, 352]]

[354, [1, 2, 3, 6, 59, 118, 177, 354]]

[356, [1, 2, 4, 89, 178, 356]]

Читайте также:  Как сделать меньше пикселей на фото

[357, [1, 3, 7, 17, 21, 51, 119, 357]]

[358, [1, 2, 179, 358]]

[360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]]

[362, [1, 2, 181, 362]]

[363, [1, 3, 11, 33, 121, 363]]

[364, [1, 2, 4, 7, 13, 14, 26, 28, 52, 91, 182, 364]]

[366, [1, 2, 3, 6, 61, 122, 183, 366]]

[368, [1, 2, 4, 8, 16, 23, 46, 92, 184, 368]]

[369, [1, 3, 9, 41, 123, 369]]

[370, [1, 2, 5, 10, 37, 74, 185, 370]]

[372, [1, 2, 3, 4, 6, 12, 31, 62, 93, 124, 186, 372]]

[374, [1, 2, 11, 17, 22, 34, 187, 374]]

[375, [1, 3, 5, 15, 25, 75, 125, 375]]

[376, [1, 2, 4, 8, 47, 94, 188, 376]]

[377, [1, 13, 29, 377]]

[378, [1, 2, 3, 6, 7, 9, 14, 18, 21, 27, 42, 54, 63, 126, 189, 378]]

[380, [1, 2, 4, 5, 10, 19, 20, 38, 76, 95, 190, 380]]

[381, [1, 3, 127, 381]]

[382, [1, 2, 191, 382]]

[384, [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 384]]

[385, [1, 5, 7, 11, 35, 55, 77, 385]]

[386, [1, 2, 193, 386]]

[387, [1, 3, 9, 43, 129, 387]]

[388, [1, 2, 4, 97, 194, 388]]

[390, [1, 2, 3, 5, 6, 10, 13, 15, 26, 30, 39, 65, 78, 130, 195, 390]]

[391, [1, 17, 23, 391]]

[392, [1, 2, 4, 7, 8, 14, 28, 49, 56, 98, 196, 392]]

[393, [1, 3, 131, 393]]

[394, [1, 2, 197, 394]]

[396, [1, 2, 3, 4, 6, 9, 11, 12, 18, 22, 33, 36, 44, 66, 99, 132, 198, 396]]

[398, [1, 2, 199, 398]]

[399, [1, 3, 7, 19, 21, 57, 133, 399]]

[400, [1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 200, 400]]

[402, [1, 2, 3, 6, 67, 134, 201, 402]]

[403, [1, 13, 31, 403]]

[404, [1, 2, 4, 101, 202, 404]]

[405, [1, 3, 5, 9, 15, 27, 45, 81, 135, 405]]

[406, [1, 2, 7, 14, 29, 58, 203, 406]]

[407, [1, 11, 37, 407]]

[408, [1, 2, 3, 4, 6, 8, 12, 17, 24, 34, 51, 68, 102, 136, 204, 408]]

[410, [1, 2, 5, 10, 41, 82, 205, 410]]

[411, [1, 3, 137, 411]]

[412, [1, 2, 4, 103, 206, 412]]

[414, [1, 2, 3, 6, 9, 18, 23, 46, 69, 138, 207, 414]]

[416, [1, 2, 4, 8, 13, 16, 26, 32, 52, 104, 208, 416]]

[417, [1, 3, 139, 417]]

[418, [1, 2, 11, 19, 22, 38, 209, 418]]

[420, [1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20, 21, 28, 30, 35, 42, 60, 70, 84, 105, 140, 210, 420]]

[422, [1, 2, 211, 422]]

[423, [1, 3, 9, 47, 141, 423]]

[424, [1, 2, 4, 8, 53, 106, 212, 424]]

[425, [1, 5, 17, 25, 85, 425]]

[426, [1, 2, 3, 6, 71, 142, 213, 426]]

[428, [1, 2, 4, 107, 214, 428]]

[429, [1, 3, 11, 13, 33, 39, 143, 429]]

[430, [1, 2, 5, 10, 43, 86, 215, 430]]

[432, [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 36, 48, 54, 72, 108, 144, 216, 432]]

[434, [1, 2, 7, 14, 31, 62, 217, 434]]

[435, [1, 3, 5, 15, 29, 87, 145, 435]]

[436, [1, 2, 4, 109, 218, 436]]

[437, [1, 19, 23, 437]]

[438, [1, 2, 3, 6, 73, 146, 219, 438]]

[440, [1, 2, 4, 5, 8, 10, 11, 20, 22, 40, 44, 55, 88, 110, 220, 440]]

[441, [1, 3, 7, 9, 21, 49, 63, 147, 441]]

[442, [1, 2, 13, 17, 26, 34, 221, 442]]

[444, [1, 2, 3, 4, 6, 12, 37, 74, 111, 148, 222, 444]]

[446, [1, 2, 223, 446]]

[447, [1, 3, 149, 447]]

[448, [1, 2, 4, 7, 8, 14, 16, 28, 32, 56, 64, 112, 224, 448]]

[450, [1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, 450]]

В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.

Как найти все делители числа

Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0 .

Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1 , — 1 , a , — a . Возьмем простое число 7 : у него есть делители 7 , — 7 , 1 и — 1 , и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1 , — 1 , 367 и — 367 .

Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a = p 1 s 1 · p 2 s 2 · … · p n s n . Тогда натуральными делителями числа a будут следующие числа: d = p 1 t 2 · p 2 t 2 · … · p n t n , где t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .

Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d , если есть такое число q , что делает верным равенство a = d · q , т.е. q = p 1 ( s 1 − t 1 ) · p 2 ( s 2 — t 2 ) · … · p n ( s n — t n ) .

Любое число, делящее a , будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p 1 , p 2 , … , p n , оно иметь не может, а их показатели в данном случае не превысят s 1 , s 2 , … , s n .

Читайте также:  Неопознанная сеть как решить проблему

Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.

Для этого нужно выполнить следующие действия:

  1. Выполнить каноническое разложение на простые множители и получить выражение вида a = p 1 s 1 · p 2 s 2 · … · p n s n .
  2. Найти все значения d = p 1 t 2 · p 2 t 2 · … · p n t n , где числа t 1 , t 2 , … , t n будут принимать независимо друг от друга каждое из значений t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .

Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.

Условие: найти все делители 8 .

Решение

Разложим восьмерку на простые множители и получим 8 = 2 · 2 · 2 . Переведем разложение в каноническую форму и получим 8 = 2 3 . Следовательно, a = 8 , p 1 = 2 , s 1 = 3 .

Поскольку все делители восьмерки будут значениями p 1 t 1 = 2 t 1 , то t 1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s 1 = 3 . Таким образом, если t 1 = 0 , то 2 t 1 = 2 0 = 1 , если 1 , то 2 t 1 = 2 1 = 2 , если 2 , то 2 t 1 = 2 2 = 4 , а если 3 , то 2 t 1 = 2 3 = 8 .

Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:

t 1 2 t 1
2 0 = 1
1 2 1 = 2
2 2 2 = 4
3 2 3 = 8

Значит, положительными делителями восьмерки будут числа 1 , 2 , 4 и 8 , а отрицательными − 1 , − 2 , − 4 и − 8 .

Ответ: делителями данного числа будут ± 1 , ± 2 , ± 4 , ± 8 .

Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

Условие: найдите все делители числа 567 , являющиеся натуральными числами.

Решение

Начнем с разложения данного числа на простые множители.

567 189 63 21 7 1 3 3 3 3 7

Приведем разложение к каноническому виду и получим 567 = 3 4 · 7 . Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t 1 и t 2 значения 0 , 1 , 2 , 3 , 4 и 0 , 1 , вычисляя при этом значения 3 t 1 · 7 t 2 . Результаты будем вносить в таблицу:

t 1 t 2 3 t 1 · 7 t 2
3 0 · 7 0 = 1
1 3 0 · 7 1 = 7
1 3 1 · 7 0 = 3
1 1 3 1 · 7 1 = 21
2 3 2 · 7 0 = 9
2 1 3 2 · 7 1 = 63
3 3 3 · 7 0 = 27
3 1 3 3 · 7 1 = 189
4 3 4 · 7 0 = 81
4 1 3 4 · 7 1 = 567

Ответ: натуральными делителями 567 будут числа 27 , 63 , 81 , 189 , 1 , 3 , 7 , 9 , 21 и 567 .

Продолжим усложнять наши примеры – возьмем четырехзначное число.

Условие: найти все делители 3 900 , которые будут больше 0 .

Решение

Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900 = 22 · 3 · 52 · 13 . Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 значения t 1 , равные 0 , 1 и 2 , t 2 = 0 , 1 , t 3 = 0 , 1 , 2 , t 4 = 0 , 1 . Результаты представляем в табличном виде:

t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4
2 0 · 3 0 · 5 0 · 13 0 = 1
1 2 0 · 3 0 · 5 0 · 13 1 = 13
1 2 0 · 3 0 · 5 1 · 13 0 = 5
1 1 2 0 · 3 0 · 5 1 · 13 1 = 65
2 2 0 · 3 0 · 5 2 · 13 0 = 25
2 1 2 0 · 3 0 · 5 2 · 13 1 = 325
1 2 0 · 3 1 · 5 0 · 13 0 = 3
1 1 2 0 · 3 1 · 5 0 · 13 1 = 39
1 1 2 0 · 3 1 · 5 1 · 13 0 = 15
1 1 1 2 0 · 3 1 · 5 1 · 13 1 = 195
1 2 2 0 · 3 1 · 5 2 · 13 0 = 75
1 2 1 2 0 · 3 1 · 5 2 · 13 1 = 975
t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4
1 2 1 · 3 0 · 5 0 · 13 0 = 2
1 1 2 1 · 3 0 · 5 0 · 13 1 = 26
1 1 2 1 · 3 0 · 5 1 · 13 0 = 10
1 1 1 2 1 · 3 0 · 5 1 · 13 1 = 130
1 2 2 1 · 3 0 · 5 2 · 13 0 = 50
1 2 1 2 1 · 3 0 · 5 2 · 13 1 = 650
1 1 2 1 · 3 1 · 5 0 · 13 0 = 6
1 1 1 2 1 · 3 1 · 5 0 · 13 1 = 78
1 1 1 2 1 · 3 1 · 5 1 · 13 0 = 30
1 1 1 1 2 1 · 3 1 · 5 1 · 13 1 = 390
1 1 2 2 1 · 3 1 · 5 2 · 13 0 = 150
1 1 2 1 2 1 · 3 1 · 5 2 · 13 1 = 1950
t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4
2 2 2 · 3 0 · 5 0 · 13 0 = 4
2 1 2 2 · 3 0 · 5 0 · 13 1 = 52
2 1 2 2 · 3 0 · 5 1 · 13 0 = 20
2 1 1 2 2 · 3 0 · 5 1 · 13 1 = 260
2 2 2 2 · 3 0 · 5 2 · 13 0 = 100
2 1 1 2 2 · 3 0 · 5 2 · 13 1 = 1300
2 1 2 2 · 3 1 · 5 0 · 13 0 = 12
2 1 1 2 2 · 3 1 · 5 0 · 13 1 = 156
2 1 1 2 2 · 3 1 · 5 1 · 13 0 = 60
2 1 1 1 2 2 · 3 1 · 5 1 · 13 1 = 780
2 1 2 2 2 · 3 1 · 5 2 · 13 0 = 300
2 1 2 1 2 2 · 3 1 · 5 2 · 13 1 = 3900

Ответ: делителями числа 3 900 будут: 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 75 , 78 , 100 , 130 , 150 , 156 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 1 300 , 1 950 , 3 900

Как определить количество делителей конкретного числа

Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a = p 1 s 1 · p 2 s 2 · … · p n s n , нужно найти значение выражения ( s 1 + 1 ) · ( s 2 + 1 ) · … · ( s n + 1 ) . О количестве наборов переменных t 1 , t 2 , … , t n мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900 , которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900 = 2 2 · 3 · 5 2 · 13 . Значит, s 1 = 2 , s 2 = 1 , s 3 = 2 , s 4 = 1 . Теперь подставим значения s 1 , s 2 , s 3 и s 4 в выражение ( s 1 + 1 ) · ( s 2 + 1 ) · ( s 3 + 1 ) · ( s 4 + 1 ) и вычислим его значение. Имеем ( 2 + 1 ) · ( 1 + 1 ) · ( 2 + 1 ) · ( 1 + 1 ) = 3 · 2 · 3 · 2 = 36 . Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

Условие: определите, сколько делителей имеет 84 .

Решение

Раскладываем число на множители.

84 42 21 7 1 2 2 3 7

Записываем каноническое разложение: 84 = 2 2 · 3 · 7 . Определяем, сколько у нас получится положительных делителей: ( 2 + 1 ) · ( 1 + 1 ) · ( 1 + 1 ) = 12 . Для учета отрицательных нужно умножить это число на 2 : 2 · 12 = 24 .

Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.

Как вычислить общие делители нескольких чисел

Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.

Разберем пару таких задач.

Условие: сколько будет натуральных общих делителей у чисел 140 и 50 ? Вычислите их все.

Решение

Начнем с вычисления НОД ( 140 , 50 ) .

Для этого нам потребуется алгоритм Евклида:

140 = 50 · 2 + 40 , 50 = 40 · 1 + 10 , 40 = 10 · 4 , значит, НОД ( 50 , 140 ) = 10 .

Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 2 0 · 5 0 = 1 , 2 0 · 5 1 = 5 , 2 1 · 5 0 = 2 и 2 1 · 5 1 = 1 0 . Значит, все натуральные общие делители исходного числа – это 1 , 2 , 5 и 10 , а всего их четыре.

Ответ: данные числа имеют четыре натуральных делителя, равные 10 , 5 , 2 и 1 .

Условие: выясните, сколько общих положительных делителей есть у чисел 585 , 315 , 90 и 45 .

Решение

Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90 = 2 · 3 · 3 · 5 , 45 = 3 · 3 · 5 , 315 = 3 · 3 · 5 · 7 и 585 = 3 · 3 · 5 · 13 , то таким делителем будет 5 : НОД ( 90 , 45 , 315 , 585 ) = 3 · 3 · 5 = 3 2 · 5 .

Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.

НОД ( 90 , 45 , 315 , 585 ) = 3 2 · 5 : ( 2 + 1 ) · ( 1 + 1 ) = 6 .

Ответ: у данных чисел шесть общих делителей.

Ссылка на основную публикацию
Сравнить технические характеристики rx330 и rx350
Линейка популярных люксовых SUV Lexus RX пополнилась новой модификацией – RX 350. Теперь покупателем RX быть еще приятнее – ведь...
Сколько рублей получают ютуберы
Видеохостинг YouTube — не только развлекательная площадка, но и хороший источник дохода. Тысячи пользователей выкладывают ролики, пытаясь привлечь внимание аудитории....
Сколько света мотает компьютер
Выбирая комплектующие для персонального компьютера (ПК) обычно обращают внимание на производительность и объем памяти, порой забывая о том, сколько же...
Сравнить процессоры кирин и снапдрагон
Snapdragon 636 vs. Kirin 960: кто лучше? Результаты тестов и сравнительных таблиц, описанных в этой статье, помогут определить, какой из...
Adblock detector