אנשים שטובים בתיכנות בסיסי - כנסו

הרוש הודף

האם זה אפשרי לתכנת אלגוריתם שהקלט שלו יהיה מספר כלשהו, והפלט שלו יהיה TRUE אם המספר ראשוני וFALSE אם לא?

KingAlpaca

בקלות רבה

הרוש הודף

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

KingAlpaca

הוא שיקר כי לעשות את זה מושלם זה בעייתי (יש המון המון מספרים ראשוניים),
אפילו עבדו על הבעיה הזאת בארץ באיזה אוניברסיטה,
אבל ברמה בסיסית זאת לא בעיה.

הפועל

אני מבטיח לך שבדיקת ראשוניות של מספרים גדולים זה משהו שעבדו ועובדים עליו הרבה יותר מאשר "בארץ באיזו אוניברסיטה" :SMOKE:

teknoboy

KingAlpaca כתב:

הוא שיקר כי לעשות את זה מושלם זה בעייתי (יש המון המון מספרים ראשוניים),
אפילו עבדו על הבעיה הזאת בארץ באיזה אוניברסיטה,
אבל ברמה בסיסית זאת לא בעיה.

מה זה "בעייתי"? או שאפשר או שאי אפשר. זה מתמטיקה, אין באמצע.

BLIzZaRd

teknoboy כתב:

KingAlpaca כתב:

הוא שיקר כי לעשות את זה מושלם זה בעייתי (יש המון המון מספרים ראשוניים),
אפילו עבדו על הבעיה הזאת בארץ באיזה אוניברסיטה,
אבל ברמה בסיסית זאת לא בעיה.

מה זה "בעייתי"? או שאפשר או שאי אפשר. זה מתמטיקה, אין באמצע.

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

KingAlpaca

הפועל כתב:

אני מבטיח לך שבדיקת ראשוניות של מספרים גדולים זה משהו שעבדו ועובדים עליו הרבה יותר מאשר "בארץ באיזו אוניברסיטה" :SMOKE:

לא, אחד המומחים הכי גדולים בעולם בזה הוא ישראלי, ברח לי השם.

KingAlpaca

teknoboy כתב:

KingAlpaca כתב:

הוא שיקר כי לעשות את זה מושלם זה בעייתי (יש המון המון מספרים ראשוניים),
אפילו עבדו על הבעיה הזאת בארץ באיזה אוניברסיטה,
אבל ברמה בסיסית זאת לא בעיה.

מה זה "בעייתי"? או שאפשר או שאי אפשר. זה מתמטיקה, אין באמצע.

תעשה לי פיבונאצ'י עם 1000 איברים.

למחשב, כמו לכל דבר, יש מגבלות.

הרוש הודף

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

אדום-עולה בבלומפילד

למה לא פשוט להריץ את כל המספרים מ-2 עד המספר חלקי 2, ולראות אם הוא מתחלק באחד מהם ללא שארית?

redblood

אדום-עולה בבלומפילד כתב:

למה לא פשוט להריץ את כל המספרים מ-2 עד המספר חלקי 2, ולראות אם הוא מתחלק באחד מהם ללא שארית?

במספרים שמספר הספרות בהם שואף לאין-סוף, יקח למחשב אין-סוף זמן לבצע פעולה כזאת.

הפועל

KingAlpaca כתב:

הפועל כתב:

אני מבטיח לך שבדיקת ראשוניות של מספרים גדולים זה משהו שעבדו ועובדים עליו הרבה יותר מאשר "בארץ באיזו אוניברסיטה" :SMOKE:

לא, אחד המומחים הכי גדולים בעולם בזה הוא ישראלי, ברח לי השם.

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

KingAlpaca

רבין, תודה.

אחד אדום

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

הפועל

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

teknoboy

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

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

אדום נחמד

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

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

KingAlpaca

יש גם תוכנית מרתקת שעשו בעקבות הספר.

עז הרים

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

החישוב הוא דיי פשוט. נניח שהמספר יכונה P. אם P הוא באמת ראשוני אז אפשר להראות שכל מספר אחר X, אם נעלה אותו בחזקת P-1 . נקבל מספר שהשארית שלו ב P שווה ל1 (משפט פרמה הקטן).

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

בחור טוב

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

ועד אז : סה"כ צריך להריץ לולאת while שמריצה מונה שמתחיל ב2 ומגיע עד ערך המספר . בתוך הלולאה בודקים אם המספר מתחלק במונה ללא שארית. במידה וכן, פסלנו את ההגדרה של מספר ראשוני והחזרנו false (מספר ראשוני מתחלק ב1 ובעצמו,וזאת אגב הסיבה שהמונה מתחיל ב-2) . אחרת , ממשיכים הלאה עד שהמונה יגיע למספר שהרצנו. במידה והמונה הגיע למספר בהצלחה סימן אפשר להחזיר true.

גיא האדום

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

ישנוני

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

teknoboy

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

אדום נחמד

עז הרים כתב:

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

החישוב הוא דיי פשוט. נניח שהמספר יכונה P. אם P הוא באמת ראשוני אז אפשר להראות שכל מספר אחר X, אם נעלה אותו בחזקת P-1 . נקבל מספר שהשארית שלו ב P שווה ל1 (משפט פרמה הקטן).

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

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

יובל

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

כיפה אדומה

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

קוד:

int NumberSqrt = sqrt(Number);
 
for(CurrentNumber=0; (Number%CurrentNumber)!=0 && CurrentNumber<NumberSqrt; CurrentNumber++)

its-sick

הרוש הודף כתב:

האם זה אפשרי לתכנת אלגוריתם שהקלט שלו יהיה מספר כלשהו, והפלט שלו יהיה TRUE אם המספר ראשוני וFALSE אם לא?

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

אחד אדום

teknoboy כתב:

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

הכוונה ששני מספרים ראשוניים גדולים הם הפקטורים

אמיר

teknoboy כתב:

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

הוא התכוון ל prime factorization.
הגורמים ראשוניים, המספר לא.

למצוא שני גורמים ראשוניים למספר ראשוני זה די פשוט...

פורום השדים האדומים

אנשים שטובים בתיכנות בסיסי - כנסו

מי מחובר

	עמוד 1 מתוך 2	[ 32 הודעות ]	עבור לעמוד 1, 2 הבא