שאלה

[coolel]

שאלה

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

 

[DNile]

א. זאת שאלה מתמטית.

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

 

[eyalbd]

למה להריץ עד לשורש?

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

 

[אילן שטרנברג]

הסיבה היא פשוטה...

בו נניח שאנחנו בודקים את המספר 101 אם הוא ראשוני. ננסה לחלק אותו ב-2 , התוצאה תהיה בערך 50. ב-3 , התוצאה תהיה בערך 33. ב-4 , התוצאה תהיה בערך 25. ב- 5 , התוצאה תהיה בערך 20. ב- 6 , התוצאה תהיה בערך 16. ב- 7 , הץוצאה תהיה בערך 14. ב- 8 , התוצאה תהיה בערך 13. ב- 9 , התוצאה תהיה בערך 11. ב- 10 , התוצאה תהיה בערך 10. ב- 11, כבר אין צורך לבדוק כיון שקיבלנו כבר את התוצאה הזו מנסיון חילוק קודם. כך שכל נסיון חילוק במספר שהוא גבוה יותר משורש המספר הנבדק כבר התקבל כתוצאה מקורבת של נסיון חילוק קודם ולכן אין צורך לבצע בדיקה של חילוק במספרים הגבוהים מהשורש. ואם אתה רוצה לשכלל את התכנית הרי שגם אין צורך לבדוק חילוק במספרים שאינם ראשוניים כיון שלדוגמא: מספר שאינו מתחלק ב-2 גם לא יתחלק ב-4. מספר שאינו מתחלק ב-3 גם לא יתחלק ב-6 או 9. בבדיקה של מספרים גדולים מאוד כדאי להציב תנאים כדי לזרז את הבדיקה. ולסיום אתגר: כתוב תכנית הבודקת את השערת גולדבך. "כל מספר זוגי הגדול מ-2 מורכב לפחות מצמד אחד של מספרים ראשוניים". ואם תצליח להוכיח את זה תהיה עשיר ומאוד מפורסם.

 

[DNile]

איפה הכסף?

bool isPrime(Integer n) { for(Integer j = 0; j < sizeof(Primes); j++) { if(Primes[j] > n) return false; else if(Primes[j] == n) return true; } } bool IsGoldBachForReal() { for(Integer i = 4; i < Infinity; i+=2) { bool bMatchesHyposis = false; for(Integer j = 0; j < sizeof(Primes); j++) { if(isPrime(i - Primes[j])) { bMatchesHyposis = true; break; } } if(!bMatchesHyposis) return false; } return true; }​

 

[אילן שטרנברג]

האם אתה יכול לשלוח תכנית מלאה?

ולעיניין: הכוונה היא להוכיח את ההשערה ולא לבדוק אותה.

 

[DNile]

שלחתי לך תוכנית מלאה..

Primes[] וInfinity הן הגדרות של השפה. חוץ מזה, בדיקת כל המספריים האפשריים זה בהחלט הוכחה. זה כמו שתגיד לי: תוכיח שעבור כל המספרים הזוגיים בתחום 0 ו6 המשוואה

x(x-1)(x-2) = x^3 -3x^2 + 2x​

מותר לי לבדוק שזה נכון ב0, 2, 4, ו6, ואם כן, לאמר שהוכחתי את מ.ש.ל. אז איפה הכסף?

 

[אילן שטרנברג]

אני רוצה להריץ את התכנית ב

visual c++

 

[DNile]

זה כבר לא חלק מהגדרת הבעיה.

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

 

[עידו123456]

שתמע,

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

אה, ואין מקדמה על החשבון...

 

[DNile]

אין כל בעיה..

אבל אני מצפה לקבל אגורה על כל יום שאני מחכה.(בערך 3.7 שקל לשנה, לא כזה הרבה)

 

[זהיר]

אהבתי את זה ../images/Emo6.gif ../images/Emo45.gif

Primes [] וInfinity הן הגדרות של השפה.

מסקנה: עדיף מחשב של 16 ביט - אצלו INF יותר קטן

חוץ מזה, בדיקת כל המספריים האפשריים זה בהחלט הוכחה. לזה אי-אפשר להתנגד!

 

[אילן שטרנברג]

נכון אבל.....

אין שום אפשרות לבדוק את כל המספרים, גם לא תיאורטית! תמיד יש עוד אחד.

 

[DNile]

אז מה שאתה בעצם אומר זה ש

i < Infinty אמור להיות i <= Infinity?

 

[coolel]

תודה אבל...

מה שכתבת פה הוא לא הסבר אלא דוגמא - אני מחפש את ההסבר ללמה זה קורה. ועוד משהו - אתה מסתתמך על בערך - איך אני יכול לבנות תכנית בהסתמכות על בערך?

 

[נועה לביא]

מה בדיוק לא הבנת?

מספיק לך לבדוק עד sqrt כי לכל x>sqrt מתקיים אם x|n (קרי: x מחלק את n) אז n\x<sqrt. למה? נניח בשלילה שn/x>sqrt, לכן x*(n\x)>sqrt*sqrt וזו סתירה כי שניהם שווים לn.

 

[DNile]

חחחחחחחחח!

גדולה

 

[עידו123456]

../images/Emo3.gif לקח לי 10 דק' לכתוב את שלי???

 

[עידו123456]

אז ככה:

קיים מספר טבעי n - אם n אינו ראשוני אזי ניתן לכתובו בצורה p*q=n כאשר p,q>1 ו p,q טבעיים. אם (p,q>sqrt(n אז p*q>sqrt*sqrt=n בסתירה להנחה המקורית, לכן נניח בה"כ כי (p<=sqrt(n ומכאן (למה? הראה כתרגיל לבית

) ש- (q>sqrt(n לכן מספיק לבדוק האם n/p נותן מספר שלם (כלומר האם n/p=q) - כלומר לבדוק רק עד (sqrt(n. █ מ.ש.ל.

 

[coolel]

דבר אחד לא הבנתי משניכם

למה: "נניח בשלילה שn/x>sqrt, לכן x*(n\x)>sqrt*sqrt" "אם (p,q>sqrt(n אז p*q>sqrt*sqrt=n" איך הגעתם לזה?