מספרים ראשוניים ב-(C++ (MFC

[טלמון סילבר]

מספרים ראשוניים ב-(C++ (MFC

שלום, שאלה כזאת: האם יש ב-MFC ספרייה של פונקציות המתייחסות למספרים ראשוניים?
למשל, פונקציה של מספר שלם ארוך(?) הבודקת אם המספר הנ"ל ראשוני ומחזירה "כן" או "לא"?

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

 

[ישעיהו בודניוק]

MFC?

 

[טלמון סילבר]

כן.

 

[טלמון סילבר]

הבהרה לגבי "מספר ארוך"

בשלב זה תספיק לי בדיקת מספרים int64__
(לא צריך להסתבך עם האלגוריתם ההודי

)

 

[הפרעתאישיותגבולית]

תחפש בגוגל

rabin miller c++
מה שמצאתי http://www.oocities.org/hmaxf_urlcr/millerrabin.htm

 

[טלמון סילבר]

תודה, מעניין!

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

 

[הפרעתאישיותגבולית]

רבין מילר

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

 

[טלמון סילבר]

תודה, אני אלך על זה.

 

[טלמון סילבר]

ישמתי את רבין-מילר

אמנם לא ב-C++ אלא בתכנית בשפת MUMPS. אכן קיבלתי שיפור מהותי במהירות, אבל לא מספיק, וגם יהיה צורך לבדוק אם לא נשארו ראשוניים מיותרים (ידועה לי הכמות הכללית שלהם).
בסביבת ה-MUMPS יש לי רשימה של כל הראשוניים בערך עד

4 * 10^8

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