המחלק המשותף הגדול ביותר באמצעות גורמים ראשוניים

מציאת גורמים נעשית איטית עבור מספרים גדולים יותר, ופירוק לגורמים ראשוניים מהיר יותר. נפרק את שני המספרים לגורמים: 45 הוא 3 × 3 × 5 ו־75 הוא 3 × 5 × 5. הגורמים הראשוניים המשותפים להם הם 3 אחד ו־5 אחד.

נכפיל את הגורמים הראשוניים המשותפים: 3 × 5 שווה ל־15, המחלק המשותף הגדול ביותר של 45 ו־75. גורם ראשוני נחשב משותף רק כמספר הפעמים שהוא מופיע בשני המספרים: ב־45 יש שני גורמי 3, אבל ב־75 יש רק אחד, לכן נכלול רק 3 אחד.

למה זה עובד: גורם משותף יכול להיבנות רק ממספרים ראשוניים ששני המספרים מכילים. לקיחת כל מספר ראשוני משותף, פעמים רבות ככל ששני המספרים מאפשרים, יוצרת את הגדול ביותר. כשיש מעריכים, לוקחים כל מספר ראשוני משותף עם המעריך הקטן יותר שלו: 3^2 × 5 ו-3 × 5^2 נותנים 3 × 5.