רוטר - איך מחשבים מספר ראשוני בפסקל?

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"איך מחשבים מספר ראשוני בפסקל?"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #8060	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 8060

BlackJack
חבר מתאריך 26.5.02
17365 הודעות

14:44 06.03.04

איך מחשבים מספר ראשוני בפסקל?

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

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
יש הרבה פתרונות יעילים יותר ויעילים	dryice	06.03.04 15:09	1
עשיתי חיפוש על המילה 'ראשוני'	BlackJack	06.03.04 15:37	5
פשוט מאוד - בדיקה...	Dudenland	06.03.04 15:13	2
תודה	BlackJack	06.03.04 15:36	4
אבל יש פתרונות יעילים באמת.	dryice	06.03.04 16:56	6
להגיד לך את האמת.. לא הנבתי כלום ממה שאמרת	ShocKi	06.03.04 18:20	7
מצטרף...	Dudenland	07.03.04 10:53	10
לא הבנתי למה אפשר לרוץ רק עד השורש של המספר	ShocKi	09.03.04 01:24	13
אז ככה	E-do	09.03.04 19:09	14
ובקשר ל trunc אני צודק או לא?	ShocKi	09.03.04 23:40	15
''ניסוי וטעיה''	E-do	10.03.04 09:58	16
צודק אתה לא תצליח להפעיל בלי trunc	The Slayer	11.03.04 20:28	17
לפחות את זה ידעתי :)	ShocKi	12.03.04 00:16	18
תודה	BlackJack	06.03.04 15:35	3
בבקשה אחי קבל	The Slayer	06.03.04 23:19	8
יש חוסר יעילות בתוכנית שלך	SpyCop	07.03.04 10:45	9
אתה צודק הייתי צריך לחלק ב2	The Slayer	07.03.04 11:45	11
פשוט את הלולאה תעשה	SpyCop	07.03.04 14:27	12

dryice

15:09 06.03.04

1. יש הרבה פתרונות יעילים יותר ויעילים
בתגובה להודעה מספר 0

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

BlackJack
חבר מתאריך 26.5.02
17365 הודעות

15:37 06.03.04

5. עשיתי חיפוש על המילה 'ראשוני'
בתגובה להודעה מספר 1

והוא מצא לי הרבה נושאים

תודה בכל זאת

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

15:13 06.03.04

2. פשוט מאוד - בדיקה...
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 06.03.04 בשעה 15:13 בברכה, Dudenland

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

לאחר שדרוגים, מספיק לבדוק מנה עבור המספרים מ-2 ועד (sqrt(n...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

BlackJack
חבר מתאריך 26.5.02
17365 הודעות

15:36 06.03.04

4. תודה
בתגובה להודעה מספר 2

ערכתי לאחרונה בתאריך 06.03.04 בשעה 15:36 בברכה, BlackJack

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

16:56 06.03.04

6. אבל יש פתרונות יעילים באמת.
בתגובה להודעה מספר 2

המתבססים על אלגברה מודרנית.
כל הפתרונות שאתה הזכרת הם למעשה אקספוננציאלים באורך המספר
(מספר הסיביות שצריך בשביל לייצג אותו)
לשימושים קריפטוגרפיים מודרניים יש צורך בעבודה עם מספרים
ראשוניים מאוד גדולים(מאות ואלפי ביטים) לא ישים לעבוד בצורה
הזאת עם מספרים בגודל כזה.
יש אלגוריתמים הסתברותיים לבדיקת ראשוניות שאפילו שבתאוריה
הם יכולים להכשל, הסיכוי שהם יכשלו הוא נמוך מהסיכוי שכל
האוויר יברח מהחדר ברגע זה ועל כן מתעלמים מאפשרות זאת.
קצת אלגברה מודרנית:
a^(p) = a mod(p) לכל p ראשוני.
יותר מכך כאשר p לא ראשוני הטענה לעיל לא תתקיים עבור לפחות
מחצית מערכי a השונים.
על כן אם נגריל k ערכי a שונים ונבדוק את השיוויון לעיל
אם בלפחות אחד מהם השיוויון לא מתקיים נדע בוודאות שp לא ראשוני.
אם בכולם השוויון יתקיים נוכל לדעת בוודאות של 1 פחות 2
בגובה -k שהמספר ראשוני. אם ניקח k=100 נוכל להיות משוכנעים
שלעולם לא נקבל תשובה שגויה.
למעשה אם נקח רק את a=2 ונבדוק נקבל וודאות מאוד טובה
גם ללא בדיקות נוספות, וברוב השימושים גם זה לא יטעה לעולם.
צריך כמובן עוד כמה תכסיסים בשביל לחשב a^p mod p ביעילות.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

18:20 06.03.04

7. להגיד לך את האמת.. לא הנבתי כלום ממה שאמרת
בתגובה להודעה מספר 6

אפשר אולי לדעת גם מה השורה התחתונה מה התנאי הסופי?
אני גם צריך את זה

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dudenland

10:53 07.03.04

10. מצטרף...
בתגובה להודעה מספר 7

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

01:24 09.03.04

13. לא הבנתי למה אפשר לרוץ רק עד השורש של המספר
בתגובה להודעה מספר 2

ערכתי לאחרונה בתאריך 09.03.04 בשעה 01:26 בברכה, ShocKi

אם אני מכניס למשל 10, אם אני ירוץ עד השורש של 10 זה 3.16
הרי שבמקרה כזה לא נגיע אפילו ל5 וזה לא נכון!...

וחוץ מזה שעושים בכלל sqrt בתנאי של הלולאה צריך להשתמש ב trunc כי יכול לצאת לך מספר לא שלם.
for I:= 2 to trunc(sqrt(n);

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

E-do
חבר מתאריך 29.10.03
2160 הודעות

19:09 09.03.04

14. אז ככה
בתגובה להודעה מספר 13

אנחנו לא צריכים להגיע ל5, כי עברנו כבר את 2
2x5=5x2=10
במקרה שלך התוכנית תרוץ עד 2 ותוציא הודעה שהמספר אינו ראשוני
העקרון פשוט, ע"מ שמספר יתחלק בזוג מספרים, חייב ש1 מהם יהיה קטן מה(או שווה ל)שורש הריבועי שלו, והשני יהיה גדול מה(או שווה ל)שורש הריבועי שלו.

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

23:40 09.03.04

15. ובקשר ל trunc אני צודק או לא?
בתגובה להודעה מספר 14

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

E-do
חבר מתאריך 29.10.03
2160 הודעות

09:58 10.03.04

16. ''ניסוי וטעיה''
בתגובה להודעה מספר 15

לדעתי אתה צודק, אבל רק הנסיון יראה את זה...

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

The Slayer
חבר מתאריך 29.4.03
7959 הודעות, 2 פידבק

20:28 11.03.04

17. צודק אתה לא תצליח להפעיל בלי trunc
בתגובה להודעה מספר 16

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

00:16 12.03.04

18. לפחות את זה ידעתי :)
בתגובה להודעה מספר 17

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

BlackJack
חבר מתאריך 26.5.02
17365 הודעות

15:35 06.03.04

3. תודה
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

The Slayer
חבר מתאריך 29.4.03
7959 הודעות, 2 פידבק

23:19 06.03.04

8. בבקשה אחי קבל
בתגובה להודעה מספר 0

http://n.rotter.net/User_files/nor/404a4034246d61e4.txt
תשנה את הסיומת ל PAS ותוכל להפעיל בפסקל

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

SpyCop

10:45 07.03.04

9. יש חוסר יעילות בתוכנית שלך
בתגובה להודעה מספר 8

ראה תגובה מספר 2.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

The Slayer
חבר מתאריך 29.4.03
7959 הודעות, 2 פידבק

11:45 07.03.04

11. אתה צודק הייתי צריך לחלק ב2
בתגובה להודעה מספר 9

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

SpyCop

14:27 07.03.04

12. פשוט את הלולאה תעשה
בתגובה להודעה מספר 11

עד השורש של המספר

נגיד קלטנו
readln(n);
אז
for i:= 2 to sqrt(n) do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד