<prompt> Unda algoriti ili kupata kigawanyo kikuu cha kawaida cha nambari mbili chanya.  <response>: Mojawapo ya algoriti maarufu na bora ya kupata kigawanyiko kikuu cha kawaida GCD cha nambari mbili chanya ni algoriti ya Euclidean. Huu hapa ni mfano wa jinsi algoriti hii inaweza kutekelezwa: def gcda, b: whileb: a, b b, a b rudisha Algoriti hii inafanya kazi kwa kutumia modulo mara kwa mara. operesheni ya kupunguza kubwa kati ya nambari mbili hadi salio iwe 0. Katika kila marudio, algoriti huweka a kwa thamani ya sasa ya b na b hadi salio wakati a inagawanywa kwa b. . Wakati b inakuwa 0, thamani ya a ni GCD ya nambari mbili asili. 