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

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

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

אסור להעלות לפה את המימוש האישי שלי, רק אציין שלמרות שעדיין אין אלגוריתם יעיל על מחשב קלאסי לפירוק לגורמים, האלגוריתם אמור להתמודד בהצלחה גם עם מספרים עצומים בהנחה שהם חזקות של 10.

מדוע זה כך?

דוגמה:

נסה לייעל את החישוב, עם או בלי שימוש בגנרטור - אולי זה יפתור חלק מהבעיות

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

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

חשבתי שאולי זה נובע מבעיות של ייצוג מספרים גדולים אבל אני לדעתי זו לא הסיבה.
באופן כללי אין הכרח לשמור את המספרים ברשימה ויהיה כנראה יותר יעיל להדפיס גורם בכל פעם אתה מוצא

לייק 1

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

אם אתה רוצה לשלוח לי את הקוד בפרטי אני אעיף מבט ואולי אוכל לסייע יותר

לייק 1

תודה רבה, שלחתי לך את הקוד בפרטי

לייק 1

ניסיתי להריץ את שלי על האייפון
ונראה דווקא שהוא שורד ומחזיר תוצאות טובות…עד כמה גדולים המספרים שאתה מנסה להכניס ?

אולי אתה עושה משו רקורסיבי ? ממה שיצא לי לנסות רקורסיה בפייטון בחלק מהאדיטורים מוגבלת למספר מסויים של הרצות

העליתי צילום למעלה של המספרים

עשית על מספר לא מספיק גבוה, נסה על 10 ** 25

לא, לא. שום רקורסיה. האלגוריתם יחסית יעיל

אפרופו, אם מישהו מוצא אלגוריתם יעיל באמת למחשב קלאסי אז יש מצב שהוא יקבל פרס טיורינג

יעני 25 אפסים כן ?

עובד רגיל.
אולי המחשב שלך רוצה לישון ? (:

אולי אתה ״צובר״ את זה למשתנה נגיד כמו רשימה או משו כזה שלוקח המון זכרון ?

ייתכן, אומרים שמחשב נהיה דומה עם הזמן לבעליו :slight_smile:

2 לייקים

מסכן אם כן המחשב שלי :woman_facepalming:t2:

שלחתי לך בפרטי את המימוש

העניין הוא שהמספרים יוצאים לא מדויקים - לאחר חלוקה ב-2 וב-5 בלבד מתקבל