שאלה לא קשה

[Morp5]

שאלה לא קשה

אני צריך אלגוריתם להצגת המחלקים הראשוניים של מספר כלשהוא כלומר על 60 אני מקבל 2 2 3 5 אני יודע שאני צריך להתחיל עם חלוקה ב2 עד שהמספר לא מתחלק ולספור כמה פעמים הוא התחלק ואז לעבור למחלק הראשוני הבא, אבל איך אני עובר למחלק הבא?? מחכה לתשובה במיטוטא תודה

 

[DNile]

כיוון כללי לפתרון:

א. מצא מחלק של המספר(אפשר לבדוק את כל המספרים מ2 עד 60) ב. הדפס את המחלק שמצאת, וחלק את המספר במחלק שמצאת ג. קיבלת מספר חדש, 60 / 2 למשל, פשוט תריץ את האלגוריתם הזה שוב פעם, כשאתה מדפיס את המחלקים של המספר החדש שנוצר לך. הסבר דוגמאתי: 60 - מתחלק ב2. תדפיס 2, ותדפיס את המחלקים של 30. 30 - מתחלק ב2. תדפיס 2, ותדפיס את המחלקים של 15 15 - לא מתחלק ב2. מתחלק ב3. תדפיס 3, ותדפיס את המחלקים של 5. 5 - לא מתחלק ב2, לא מתחלק ב3, לא מתחלק ב4, מתחלק ב5, תדפיס 5, ואל תדפיס את המחלקים של 1.

 

[DNile]

אידיוט, זה לא כיוון כללי,

ממש פתרת לו את הבעיה.

 

[Morp5]

אני יודע, אחרי זה בדיוק נתקעתי, איך

אני עובר מ 2 ל3 וכך הלאה? הרי אי אפשר לעשות לולאה לכל מחלק.

 

[DNile]

וכי למה לא?

 

[Morp5]

../images/Emo12.gif האם דיברת עם עצמך כרגע?

תודה אבל ההודעה שלך לא חידשה לי הרבה

 

[Morp5]

יש רק 5 מחלקים ראשוניים?

מה עם 7 11 13 17 לא נחשבים?

 

[עידו123456]

השאלה היא כזאת

האם אתה מסתפק בפתרון פשוט לבעיה (כמו זה שהציע DNile) או שאתה מעלה את הסיבוך של השאלה לרמה של לקבוע האם מספר הוא ראשוני או לא (שזה אלגוריתם בפני עצמו) השאלה השניה מתחלקת עוד פעם לכמה תת-שאלות: האם אתה מחפש פתרון פשוט (לבדוק האם מספר n מתחלק באיזשהו מספר בין 2 ל (sqrt אלא שאז לא חסכת כלום בבעיה המקורית. או שאתה מחפש פתרון יותר מסובך כמו אלגוריתמים הסתברותיים (Rabin-Miller לדוגמא) או אלגוריתם דטרמיניסטי כמו ה - AKS החדש. שני הפתרונות האחרונים (אלגוריתם הסתברותי/דטרמיניסטי) מעלים את הסיבוך בפתרון לרמה מאוד גבוהה, אלו לא אלגוריתמים פשוטים - בהחלט בכמה רמות מעבר לרמת השאלה המקורית.

 

[נועה לביא]

אין פתרון יעיל לבעיית הפירוק לגורמי

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

 

[עידו123456]

את צודקת

אבל אני לא בטוח שמהסיבה המתאימה (לא כל-כך הבנתי את מה שכתבת) אין סיבה לבדוק אם מספר הוא ראשוני או לא, כי הבדיקה האם מספר i הוא גורם של n היא פשוטה יותר ( (O(1 לכל i ) מאשר לבדוק קודם האם i הוא ראשוני ( (O(log n בחזקת משהו לכל i בשיטות המהירות) ורק אז לבדוק האם הוא גורם של n. יש טעם לעומת זאת להכין מראש טבלה קצרה של ראשוניים (משהו כמו 20 המספרים הראשוניים הראשונים) ולעבוד לפיה (כלומר לבדוק האם המס' מתחלק באחד מ- 20 המספרים הנ"ל - ורק אם הוא לא אז להתחיל לעבור בצורה איטרטיבית על שאר המספרים האי זוגיים)

 

[נועה לביא]

כן, לזה התכוונתי...

הכותרת הייתה סתם הערה שהתחשק לי להוסיף...

 

[eyalbd]

אלגוריתמים לא חסר

מצורף קישור. רק תיזהר לא לטבוע שם. השיטה של DNILE טובה אבל עבור מספרים ענקיים דרוש משהו יותר מתוחכם. מתימטיקאים המציאו הרבה שיטות אבל אין אחת general purpose שטובה יותר מהשאר.

 

[Morp5]

למה מספרים ענקיים? מה עם 121

הרי לא הגיוני לכתוב לולאות עד שאני מגיע ל 11 חששתי שאין דרך פשוטה ל"דלג" בין המחלקים לכן נתקעתי.

 

[Morp5]

OK מצאתי פתרון תגידו לי מה אתם

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

 

[Morp5]

טוב כמובן שטעיתי, אני מגיע למספרים

לא ראשוניים.... יש לי את התוכנית מוכנה בקובץ EXE איך אני פותח אותו ב ms vc כדי לראות מה כתוב בקוד שלו?