חידה 3: הגורם הראשוני (Prime Factor) הגדול ביותר

החידה:
הגורמים הראשוניים של 13195 הם 5, 7, 13 ו-29.
מהו הגורם הראשוני הגדול ביותר של המספר 600851475143?

קישור למקור


מושגים להבהרה:

  • מספר ראשוני:

מספר ראשוני הוא מספר טבעי גדול מ-1, שלא ניתן להציגו כמכפלה של שני מספרים טבעיים קטנים ממנו, כלומר הוא מתחלק רק ב-1 ובעצמו. מספר טבעי גדול מ-1 שאינו ראשוני נקרא מספר פריק. המספר 1 אינו נחשב ראשוני, וגם לא פריק… לפי “המשפט היסודי של האריתמטיקה”, כל מספר טבעי גדול מ-1 אפשר להציג באופן יחיד כמכפלה של מספרים ראשוניים (למשל: 28 = 7 × 2 × 2 {\displaystyle \ 28=7\times 2\times 2} \ 28 = 7\times 2\times 2). ההצגה הזו יחידה עד כדי שינוי סדר. ראשוניים אלה נקראים גורמים של המספר. בלשון מודרנית, אומרים שחוג המספרים השלמים הוא “תחום פריקות יחידה”.

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

מתוך ויקיפדיה

כמה רמזים בדרך לפתרון:

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

הפיתרון שלי:

לייק 1