עץ פקטוריזציה ראשוני

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

כלל הפיצול הוא חלוקה נסיונית לפי הראשוני הקטן ביותר האפשרי בכל שלב: נסה תחילה 2, ואז מספרים אי-זוגיים 3, 5, 7, 9... עד לשורש הריבועי של הערך הנוכחי. עבור 360 זה מופיע בתור 360 = 2 × 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) ומדווח על הודעה כנה מעבר לכך במקום להקפיא את הכרטיסייה - לדפדפן אין עסק לתלות רק על נקודת חצי-פריים ענקית.

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