უსგ და ერატოსთენეს საცერი

უდიდესი საერთო გამყოფი უსგ(a, b) ის უდიდესი რიცხვია, რომელიც ორივეს ყოფს. ყველა კანდიდატის ცდა ნელია. ევკლიდემ შენიშნა, რომ a-სა და b-ს ყოველი საერთო გამყოფი a mod b-საც ყოფს, რადგან a mod b = a − q·b. ამიტომ

gcd(a, b) = gcd(b, a mod b) და gcd(a, 0) = a.

84-ისა და 60-ისთვის: (84, 60) → (60, 24) → (24, 12) → (12, 0), ანუ პასუხი 12-ია სამი გაყოფის შემდეგ. კოდში ერთი სტრიქონია: while (b) { t = a % b; a = b; b = t; }.

უსგ-ს ცოდნით უმცირესი საერთო ჯერადიც მარტივად მიიღება: lcm(a, b) = a / gcd(a, b) * b. ჯერ გაყავი, რომ შუალედური მნიშვნელობა არ გადაივსოს.

ჩაწერე 2..n და ყველა მონიშნე „შესაძლოა მარტივად“. p-ს ზემოთ მივყვეთ. თუ p ჯერ კიდევ გადაუხაზავია, ის მარტივია, რადგან მასზე მცირე არცერთი მარტივი არ ყოფს. შემდეგ ვხაზავთ მის ჯერადებს. ორი დეტალი ხდის სწრაფს:

• ხაზვას ვიწყებთ p²-დან: უფრო მცირე ჯერადები, მაგ. 2p და 3p, 2-მა და 3-მა უკვე გადახაზეს
• ვჩერდებით, როცა p² > n: ყოველ შედგენილ რიცხვს ≤ n აქვს მარტივი გამყოფი ≤ √n, ამიტომ დარჩენილი ყველა მარტივია

for p in 2..: if p*p > n break; if is[p]: for m = p*p; m <= n; m += p: is[m] = false

სრული შრომა მარტივებზე n/2 + n/3 + n/5 + … ჯამია, რაც O(n log log n)-ია: პრაქტიკულად წრფივი. საცერი 10^7-მდე წამზე გაცილებით სწრაფად სრულდება და თითო რიცხვზე ერთ ბაიტს (ან ერთ ბიტს) მოითხოვს.