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

[TeaTime]

כן אני מכיר את האלגוריתם הזה

הוא די מדויק ומשמש בעיקר למספרי ענק (השימוש העיקרי שלו זה פיצוח צפני הRSA)

[nsof]

sorry holy אבל כמעט תמיד יהיה עדיף לחשב את השורש.

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

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

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

http://www.cse.iitk.ac.in/news/primality.html