עץ גורמים ראשוניים

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

כלל הפיצול הוא ניסוי חלוקה בראשוני הקטן ביותר האפשרי בכל שלב: מנסים קודם לחלק ב-2, ואז במספרים האי-זוגיים 3, 5, 7, 9... עד לשורש הריבועי של הערך הנוכחי. עבור 360 זה מתבטא כך: 2 = 360 × 180, אחר כך 180 = 2 × 90, אחר כך 90 = 2 × 45, אחר כך 45 = 5 × 9, ואחר כך 9 = 3 × 3 – חמישה פיצולים שמסתיימים בשישה עלים ראשוניים (2, 2, 2, 3, 3, 5). ספירת העלים האלה נותנת את צורת החזקות המקוצרת המוצגת מתחת לתרשים: 360 = 2³ × 3² × 5.

כל זה רץ עם חישובי BigInt מדויקים, כך שאין שום עיגול של נקודה צפה בדרך למטה. ניסוי חלוקה עד השורש הריבועי הוא מהיר עבור מספרים יום-יומיים, אך נעשה איטי יותר ככל שהגורם הראשוני הקטן ביותר של הקלט גדול יותר, לכן הכלי מגביל את הקלט ל-1,000,000,000,000 (10 בחזקת 12) ומציג הודעה כנה מעבר לכך במקום לקפוא – דפדפן לא אמור להיתלות על חצי-ראשוני ענק רק כדי להוכיח נקודה.

עץ גורמים חזותי הוא הדרך המקובלת שבה מלמדים פירוק לגורמים ראשוניים בבית הספר, והוא ממשיך לשמש גם הרבה אחרי הכיתה: צמצום שברים, מציאת הגורם המשותף הגדול ביותר או הכפולה המשותפת הקטנה ביותר על ידי השוואת חזקות ראשוניות, פישוט שורשים ריבועיים, ובדיקה מהירה אם מספר הוא ראשוני – כל אלה חוזרים לאותו פירוק. הכל רץ מקומית בדפדפן שלכם – בלי הרשמה, בלי פניה לשרת.