Тақсимкунандаҳо бо санҷиш
d n-ро тақсим мекунад, вақте ки n % d == 0. Барои ёфтани ҳамаи тақсимкунандаҳо ҳар d-ро аз 1 то n санҷед:
Барои 36 чоп мешавад:
Адад комил аст, агар он ба ҷамъи тақсимкунандаҳои аз худаш хурд баробар бошад. Масалан, 6 = 1 + 2 + 3. Давр бо ҷамъкунак ҷамъро меёбад:
Барои 28 28 ва YES чоп мешавад: тақсимкунандаҳои 1, 2, 4, 7 ва 14 ҷамъашон 28 мешавад. Барои 12 16 ва NO чоп мешавад.
Ададҳои сода ва ҷойи қатъ
Адади сода дақиқан ду тақсимкунанда дорад: 1 ва худаш. Адади 1 сода нест. Пас n сода аст, агар ягон d аз 2 то n - 1 онро тақсим накунад. Ва ҷустуҷӯро дар аввалин d-е, ки тақсим мекунад, қатъ кардан мумкин аст:
Барои 91 NO чоп мешавад ва барои 97 YES чоп мешавад.
Чаро дар d * d <= n қатъ мекунем? Тақсимкунандаҳо ҷуфт-ҷуфт меоянд. Агар n = a * b, яке аз a ва b аз решаи квадратии n зиёд нест. Пас агар n умуман тақсимкунанда дошта бошад, онро то ҳамон ҷо меёбед. Барои n = 36 ҷуфтҳо чунинанд: 1 · 36, 2 · 18, 3 · 12, 4 · 9 ва 6 · 6. Баъди 6 ҷуфтҳо бо тартиби дигар такрор мешаванд.
Барои n то 10⁵ ҳатто давр то n кифоя тез аст. Барои адади дувоздаҳрақама танҳо давр то решаи квадратӣ тез аст: як миллион қадам, на як триллион. Ин даври while аст: қатъ ба худи d вобаста аст.
Бузургтарин тақсимкунандаи умумӣ
Бузургтарин тақсимкунандаи умумӣ (gcd)-и ду адад калонтарин ададе аст, ки ҳардуро тақсим мекунад. Евклид пай бурд, ки он тағйир намеёбад, агар адади калонтар бо бақияи тақсим иваз шавад: gcd(a, b) = gcd(b, a % b). То бақия 0 нашавад, такрор кунед.
aваb-ро хонед. Бузургтарин тақсимкунандаи умумии онҳоро чоп кунед.
Вуруд
Баромад
Барои 84 ва 36: 84 % 36 ба 12 баробар аст, баъд 36 % 12 ба 0. Пас gcd ба 12 баробар аст. Ададҳо зуд хурд мешаванд: сад қадам ҳатто барои ададҳои наздик ба 10¹⁸ кифоя аст.
a, b = b, a % b ҳарду номро якбора тағйир медиҳад. Тарафи рост аввал бо a ва b-и кӯҳна ҳисоб карда мешавад. Агар ба ду сатр навишта шавад, a = b пеш аз ҳисоб шудани , -ро нест мекард.
