פירוק מספר לגורמים ראשוניים

המשפט היסודי של האריתמטיקה אומר כי אפשר לפרק כל מספר טבעי (כלומר שלם חיובי) לגורמים ראשוניים, והפירוק הזה הוא יחיד. (סדר הגורמים אינו משנה)

למשל, את המספר 40 ניתן לפרק לגורמים הראשוניים הבאים: 2 * 2 * 2 * 5 = 2³ * 5¹ = 40.

המספרים 2 ו-5 הם מספרים ראשוניים. (כזכור, מספר ראשוני הוא מספר שמתחלק רק ב-1 ובעצמו ללא שארית).

אך חלק מהמספרים הם מכפלה של שני מספרים ראשוניים בלבד.

לדוגמה,

• המספר 35 הוא מכפלה של 5 ו-7.
• המספר 493 הוא מכפלה של 17 ו-29.
• המספר 8509 הוא מכפלה של 67 ו-127.

נתונה השיטה הבוליאנית הבאה (אין צורך לממש אותה):

isHighFactorInRange המקבלת מספר טבעי n ו-2 מספרים low ו-high אשר מייצגים שני קצוות של טווח חיפוש. ו- n הוא מכפלה של בדיוק שני מספרים ראשוניים p ו-q. השיטה בודקת האם הגורם הראשוני הגדול מבין p, q נמצא בטווח החיפוש. אם כן היא מחזירה true, אחרת היא מחזירה false (טווח החיפוש כולל את הקצוות).

לדוגמה, המספר 8509 הוא מכפלה של 67 ו-127. לכן, אם תופעל השיטה isHighFactorInRange עם המספר n = 8509 וטווח החיפוש low = 1, high = 100 השיטה תחזיר false כיוון שהגורם הראשוני הגדול יותר מבין 67 ו-127 הוא 127, והוא לא נמצא בטווח בין 1 ל-100. ואילו עבור הטווח low = 1, high = 200 השיטה הייתה מחזירה true, כי 127 הוא בין 1 ל-200.

בהינתן מספר שלם חיובי n שהוא מכפלה של בדיוק שני מספרים ראשוניים p ו-q. יש למצוא ולהדפיס את p ו-q.

לדוגמה, עבור n=8509 השיטה תדפיס 67 ו-127 מאחר ו 67*127=8509.