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

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

אין לי מושג איך לבדוק בעזרת פסקל אם המספר ראשוני... תודה מראש!

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

שורש, אם אני זוכר נכון, בפסקל זה SQRT.

הבנתי איך לבצע את הרעיון שלך, לא הבנתי למה דווקא שורש הוא זה שצריך להיות גבול הבדיקה ?

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

ואם הוא קטן יותר אז כבר בדקת אותו.

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

נכון, ואם הם לא שווים אז אחד מהם בהכרח יותר קטן מהשורש, וכך תבדוק את כל המכפילים האפשריים.

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

למשל, עבור המספר 16.

עלייך לעבור עד המספר 4.

16/1=16 מתחלק ללא שארית

16/2=8 מתחלק ללא שארית

16/3 מתחלק עם שארית

16/4=4 מתחלק ללא שארית

תשים לב שאם תמשיך ל-5, 6, 7, 9, 10, 11, 12, 13, 14, 15 הם יתחלקו לך עם שארית

וגם את המספרים 8 ו- 16 שמחלקים את 16 ללא שארית מצאת כשחילקת ב- 1 ו- 2, לכן אתה לא צריך לבדוק אותם שוב.

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

סתכל על זה לפי הגיון-

נגיד המספר שלך הוא N. והשורש שלו הוא X . אז - X*X=N .

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

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