Тақсимкунандаҳо
d тақсимкунандаи n аст, вақте ки n % d == 0. Барои ёфтани ҳамаи тақсимкунандаҳо ҳар d-ро аз 1 то n санҷед.
n-ро хонед. Ҳамаи тақсимкунандаҳои онро аз хурдтарин чоп кунед.
Вуруд
Баромад
Агар дар if ҳисобкунак ё ҷамъкунак гузорем, ҳамин сикл тақсимкунандаҳоро мешуморад ё ҷамъ мекунад. Адад комил аст, агар он ба ҷамъи тақсимкунандаҳояш, ки аз худи он хурданд, баробар бошад: 6 = 1 + 2 + 3.
n-ро хонед. Ҷамъи тақсимкунандаҳояшро, ки азnхурданд, чоп кунед, ваYES, агарnкомил бошад.
Вуруд
Баромад
Тақсимкунандаҳои 28, ки аз он хурданд, 1, 2, 4, 7 ва 14 мебошанд ва ҷамъашон 28 мешавад.
Ададҳои сода
Адади сода дақиқан ду тақсимкунанда дорад: 1 ва худи он. Адади 1 сода нест, зеро он танҳо як тақсимкунанда дорад. Пас n сода аст, агар ягон d аз 2 то n - 1 онро тақсим накунад. Ҷустуҷӯро дар аввалин d, ки тақсим мекунад, қатъ кардан мумкин аст.
Қатъ кардан бисёр барвақттар мумкин аст. Тақсимкунандаҳо ҷуфт-ҷуфт меоянд: агар n = a · b, пас яке аз a ва b аз √n зиёд нест.
Пас, агар тақсимкунанда бошад, он пеш аз он пайдо мешавад, ки d * d аз n гузарад.
n-ро хонед.YES-ро чоп кунед, агар сода бошад, ваNO-ро, агар не.
Вуруд
Баромад
Барои n то 10⁵ сикл то n кофӣ тез аст. Барои 10¹² танҳо сикли то √n тез аст: як миллион қадам ба ҷои як триллион. d навъи long long дорад, то d * d пур нашавад.
Бузургтарин тақсимкунандаи умумӣ
ТУК-и ду адад — бузургтарин ададест, ки ҳардуро тақсим мекунад. Евклид пай бурд, ки ТУК тағйир намеёбад, агар адади калонро бо бақияи тақсимаш иваз кунем: gcd(a, b) = gcd(b, a % b). Онро такрор кунед, то бақия 0 шавад. Охирин адади аз нул фарқкунанда ТУК аст.
Барои 84 ва 36: 84 % 36 = 12, баъд 36 % 12 = 0. Пас ТУК ба 12 баробар аст.
Ду адад байни худ сода мебошанд, агар ТУК-и онҳо 1 бошад. Хурдтарин зарби умумии онҳо (КУХ) ба a / gcd * b баробар аст. Аввал тақсим кунед, то зарб пур нашавад.
