שלום לכלום המורה הביא לנו תרגילים לפתור ב c++ אם תוכלו לעזור אני אודה לכם מאוד

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

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

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

תודה מראש למי שעוזר

אני מניח שלמדתם פונקציות ושהתכוונו שתעשו את זה עם פונקציות.

תוכנית ראשונה:

[code=cpp]
[code]#include <iostream.h>

int ri(int n){
	for(int i=2;i<n/2;i++)
		if(n%i==0)
			return 0;

	return 1;
}

void main(){
	int n;

	cout<<"Please enter a number."<<endl;
	cin>>n;

	if(ri(n)==0)
		cout<<"The number is parik."<<endl;

	else
		cout<<"The number is rishoni."<<endl;
}

תוכנית שנייה:

[code]#include <iostream.h>

int ri(int n){
	for(int i=2;i<n/2;i++)
		if(n%i==0)
			return 0;

	return 1;
}

void main(){
	int n;

	cout<<"Please enter a number."<<endl;
	cin>>n;

	for(int i=1;i<=n;i++){
		if(ri(i)==0)
			cout<<"The number "<<i<<" is parik."<<endl;

		else
			cout<<"The number "<<i<<" is rishoni."<<endl;
	}
}

עריכה: יש צורך רק לתקן לגבי המספר 1 שהוא לא ראשוני ולא פריק ו-0 שהוא לא חוקי.

ובמקום לחלק את -N ב-2 אפשר לעשות גם שורש

היה על זה ויכוח פעם מה יותר יעיל

פתרון עבור הראשון:

http://en.wikipedia.org/wiki/Fermat_primality_test

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

פתרון עבור השני:

בונים מערך עם המספרים 0 עד n ומאפסים את מקום 1 (ככה שהמערך הוא 0,0,2,3,4...)

עכשיו עבור כל תא במערך:

- אם התא מכיל 0, נדלג לתא הבא.

- אחרת, נאפס התאים בכל הכפולות של אותו מקום (למעט אותו תא) (כלומר אם אנחנו ב-3, אז נאפס את תאים 6,9,12,15, וכן הלאה)

בסופו של דבר כל התאים שאינם 0 הם מספרים ראשוניים.

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

אז יש פה טעות איפשהוא

כי לא איפסת את כל הכפולות של 2.

ובמקום לחלק את -N ב-2 אפשר לעשות גם שורש

היה על זה ויכוח פעם מה יותר יעיל

בקשר לתרגיל הראשון - ברור שלרוץ עד שורש N זה הרבה יותר יעיל מאשר לרוץ עד N/2 (קח למשל N = 1,000,000 וכבר תראה הבדל בפועל).

תרוץ על i קטן-שווה לשורש N (כי אחרת 25 יעשה בעיה. אולי זו הבעיה שיש לך עם 4).

שיפור נוסף למה ש- orlupo הציע: תבדוק האם המספר מתחלק ב-2 בנפרד. בלולאה תרוץ מ-3 ומעלה, ובמקום

++ i

תעשה

2 =+ i

אין טעם לבדוק עבור 4,6,8... וכו' כי כולם זוגיים. ככה עושים רק חצי מהבדיקות.

בקשר למה ש-שניצל אמר: מדובר באלגוריתמים הסתברותיים [זה הכרחי כי לפעמים המספרים גדולים מאוד ואי אפשר לבדוק ראשוניות בשיטה הנאיבית וחייבים להסתמך על כל מיני היבטים מתמטיים תאורטיים]. זה נושא מאוד עמוק ודי מסובך ואתה ממש, אבל ממש, לא רוצה להכנס לזה בשביל תרגילון קטנטן ב- c++ !

אבל עצם החישוב של השורש יכול לקחת יותר זמן מזמן הריצה של הלולאה...

אבל עצם החישוב של השורש יכול לקחת יותר זמן מזמן הריצה של הלולאה...

בדיוק על זה התווכחנו אז

אבל עצם החישוב של השורש יכול לקחת יותר זמן מזמן הריצה של הלולאה...

ממש, אבל ממש לא סביר (עבור בעיות "מעניינות").

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

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

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

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

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

ניסיתי לחפש מידע על כמה פעולות לוקח לעשות את פעולות החישוב האלה ולא מצאתי.

אבל אפילו אם מדובר במספר מאוד קטן, נגיד 100 :

לרוץ עד שורש 100 זה 10 איטרציות של הלולאה.

לרוץ עד 100/2 זה 50 איטרציות.

מדובר בהפרש של 40 איטרציות במקרה הזה.

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

40 איטרציות * מספר הפעולות בכל איטרציה = המון המון פעולות שחוסכים (אל תשכחו שאפילו משהו פשוט כמו i++ לוקח 3-4 פעולות מעבד).

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

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

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

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

כבד כבד

בייחוד או השורש לא שלם

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

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

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