אתה יכול לפתור את השאלה הזאת בצורה הרבה יותר חכמה...

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

כלומר להריץ לולאה מ20 עד 700 כאשר עבור כל מספר אתה בודק אם הוא מתחלק ב2 עד השורש הטבעי של המספר.

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

להלן הקוד הרצוי:

#include <stdio.h>

#include <conio.h>

#include <math.h>

void main ()

{

int rishoni,root,i,j;

clrscr();

for (j=20;j<=700;j++)

{

root=sqrt(j);//the natural square root

i=2;

rishoni=1;//the flag

while (i<=root && rishoni==1)

{

if (j%i==0)

rishoni=0;//the number isn't rishoni

i++;

}

if (rishoni==1)//if no number was divided completely

printf("the number %d is rishoni.\n",j);

}

}

vega הקוד שלו לא עובד כי ב-for עושים ; ולא ,

A.S.A.P - חישוב שורש די יקר (בעיקרון כל פעולה על מספרים עם נקודה צפה די יקרה), לדעתי עדיף לבדוק עד המספר חלקי 2 בשביל לקבל ביצועים מקסימליים.

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

אין לי ממש כוח להסביר אבל נסו להבין

טוב נו ניתן כמה דוגמאות

2 ראשוני

3 לא מתחלק ב2 ולכן ראשוני

4 מתחלק ב2= לא ראשוני

5 לא מתחלק לא ב3 ולא ב 2 = ראשוני

6 מתחלק ב2 = ראשוני

7 לא מתחלק באף אחד מהמספרים הראשוניים שלהלן(2,3,5) ולכן ראשוני

וכך הלאה

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

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

אם לא מצאנו אז המספר ראשוני

A.S.A.P - חישוב שורש די יקר (בעיקרון כל פעולה על מספרים עם נקודה צפה די יקרה), לדעתי עדיף לבדוק עד המספר חלקי 2 בשביל לקבל ביצועים מקסימליים.

מבחינת ביצועים "נטו" של המחשב עדיף לחפש עד מחצית המספר,

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

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

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

מבחינת זמן ריצה וחיסכון בזיכרון הכי יעיל לבדוק עד מחצית המספר.

ניראה לי ששלי יותר יעיל

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

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

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

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

מבחינת זמן ריצה וחיסכון בזיכרון הכי יעיל לבדוק עד מחצית המספר.

זה גם בזבזני

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

זה בזבזני מעוד סיבה

תחשוב שניה על המספר 200 אבל בוא נלך אחורנית

נבדוק שהוא מתחלק ב100 וואלה אנחנו שמחים

עכשיו בלי לנסות לחשב תגיד לי אם אני באמת הייתי צריך לבדוק את החלוקה של 200 ב 99 או לחילופין ב 98

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

אתה צודק בהחלט!

לפי השיטה של בדיקה עד מחצית המספר סורקים בשיטה איטרטיבית (לולאה) את כל המספרים מ2 עד מחצית המספר,

וכאשר מגלים התחלקות מפסיקים את הבדיקה!

כלומר המספר 200 מתחלק ב2 ואחרי בדיקה אחת בלבד הפסקנו לבדוק.

אבל במקרה בו המספר הוא אכן ראשוני המצס שונה לחלוטין - כאן יכול להיות הבזבוז:

בין 20 ל700 ישנם 117 מספרים ראשוניים (בדיקה ע"י מחשב). אם הינו בודקים במצב הגרוע ביותר עד מחצית המספר אז היינו בודקים 349 מספרים - אכן יש כאן בזבוז.

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

לעומת זאת אם היינו בודקים רק עד שורש המספר, במצב הגרוע ביותר היינו סורקים 25 מספרים בלבד(מ2 עד 26[שורש ריבועי טבעי של 700])!

אך כאן יש חישוב שורש שהוא דיי מסורבל...

כן אבל יש פגם אחד

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

משום מה יש לי הרגשה שהיא בעצמה עושה נסיונות וצורכת המון משאביי מערכת

בכל מקרה אי אפשר להימנע מזה

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

השאלה מה יותר יקר

זיכרון או זמן מעבד?

שאלה ממש טובה...

הייתי אומר שבשביל תוכנית של תלמיד הלומד מדעי המחשב הדבר החשוב ביותר הוא פיתרון חכם, יצירתי ויעיל מכל הבחינות. 8)

נכון

אני חושב שאם מורה רואה דרך יצירתית הוא ישר רואה את התלמיד בצורה אחרת

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

נכון שהתוכנית הייתה עובדת אבל מה עשינו פה?

לפי דעתי ווגה קח פה את כל הרעיונות שנאמרו ותציג למורה שלך מספר אפשרויות שונות לפיתרון

אני בטוח שתקבל על זה הערכה נוספת

שורש של מחשב הוא לא פעולה בזבנית כל כך

ואני די בטוח שהיא פחות בזבזנית מלולאה

המחשב לא "מנחש" את השורש

יש טור מתמ' שהוא משתמש בו ו

אם אתה מנסה לחשב שורש אינטג'רי

אני חושב שהטור הוא בעל 3 או 4 איברים

מה שיוסיף רק 3 או 4 איטרציות יותר פר מספר אבל יחסוך 100+ איטרציות של לעבור על המספרים עד החצי

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

קחו מספר כמו n=10^20=100000000000000000000.

כמות האיטרציות עד n*0.5 תהיה 0.5n=0.5*10^20=50000000000000000000

כמות האיטרציות עד(sqrt(n תהיה 10000000000 =10^10=(sqrt(n

חישוב השורש יקח (ונהיה large) מקסימום 10 איטרציות.

היחס בין הכמויות הוא

50000000000000000000 / (10000000000 + 10) = ~5000000000 = 0.5*10^10

כלומר אם היה לוקח לבצע את האלגוריתם של השורש שניה אחת האלגוריתם עד החצי היה לוקח (שימוש קל במחשב  ) 1388888 שעות שהם 57870 ימימ שהם 158 שנים!!!!!!!

לגבי הרעיוך להשתמש בחלוקה רק במספרים שידוע כבר שהם ראשוניים (ע"י Burton) מעולה!!!! 

הרעיון כמובן לא חדש ומבוסס על הנפה של אריסטוטנס( :ylsuper:) והרעיון הוא בדיוק מה ש - Burton אמר.

לגבי המקום שזה ידרוש (והעובדה שגודל זה לא ידוע מראש).

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

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

בסדר, נכון , אני מסכים שענין תאורטי/אקדמי לחלוטין וכבר בטח Vega קיבל 100 אבל סתם בא לי.

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

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

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

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

הטור מתכנס במהירות אדירה ואפשר לחשב אותו אינטג'רית

מה שמאפשר 2-3 איטרציות עד לתשובה של 0.1 מהאמיתית (כלומר האינטג'ר עצמו)

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

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

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

לגבי הרעיוך להשתמש בחלוקה רק במספרים שידוע כבר שהם ראשוניים (ע"י Burton) מעולה!!!!

הרעיון כמובן לא חדש ומבוסס על הנפה של אריסטוטנס( :ylsuper:) והרעיון הוא בדיוק מה ש - Burton אמר.

תודה תודה ;D האמת שחשבתי עליו בעצמי אבל כששאלתי את אבא שלי גם הוא העלה את אותו רעיון ועכשיו אתה גם אומר שזה דבר מוכר(האמת לא שיערתי שאני הראשון אבל זה היה בלתי תלוי)

דרך אגב אבא שלי אמר לי שיש שיטות הרבה יותר יעילות שמשתמשות בהסתברות כדי לקבוע אם בכלל כדאי להשתמש באלגוריתם המלא

יש מקרים שההסתברות קובעת מראש שבכלל לא כדאי ואפשר מראש לשלול את המספר

אם תירצו אני מחר אברר עוד בנושא ההסתברות