ברצוני לכתוב תוכנית C++ שבודקת האם מספר כלשהו הוא ראשוני. מה עלי לבדוק?

[assaf990]

האם לבדוק האם מהמספר 2 ועד למספר הנתון אין שארית אפס (מלבד המספר עצמו)

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

[blabla2002]

אתה עושה

#include <iostream.h>

int main()
{
int num,i,flag=0;
cout << "Enter num ";
cin >> num;
for (i=2 ; i<num ; i++)
{
if (num%i==0)
{
flag=1;
break;
}
if (num/i<2)
break;
}
if (flag==1)
cout <<"not prime" << endl;
else
cout <<"prime" << endl;
return 0;
}

#include <stdio.h>

[Boomerang]

אתה יכול להפסיק בשורש, כי אם המספר X מתחלק במספר Y שגדול מהשורש שלות אז X גם מתחלק ב- (X/Y) שקטן מהשורש של X, ועליו כבר עברת

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

[Ghosthunter]

קוראים לאלגו רבין קארפ משהו בסגנון מבחן פרמה התבלבלתי עם השני. אם אתה רוצה לבדוק אם N הוא ראשוני, אתה בוחר מספר רנדומאלי A בין 1 ל N. אתה בודק אם a^(n-1)mod n==1 אם כן אזי הוא ראשוני(הסתברותית) אם לא אז הוא כנראה פריק.

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

למשל:

N=(561)₁₀=(b1b2b3b4...)₂

כל איטרציה אתה מחשב את:

a^kmodnב- O(1)

אם אתה מקבל 1 אז אתה יכול להפסיק.

הסיבוכיות היא o(l^3) כאשר l זה מספר הביטים.

תחפש בגוגל(או בוויקי) את החישוב שרשמתי למעלה אם לא הבנת.

[assaf990]

אתה יכול להפסיק בשורש, כי אם המספר X מתחלק במספר Y שגדול מהשורש שלות אז X גם מתחלק ב- (X/Y) שקטן מהשורש של X, ועליו כבר עברת

את זה חיפשתי, היכן אני יכול למצוא הוכחה מתמטית על כך?

(בננה צהובה - תודה רבה על ההשקעה...)

[שניצל]

קוראים לאלגו רבין קארפ משהו בסגנון. אם אתה רוצה לבדוק אם N הוא ראשוני, אתה בוחר מספר רנדומאלי A בין 1 ל N. אתה בודק אם a^(n-1)mod n==1 אם כן אזי הוא ראשוני(הסתברותית) אם לא אז הוא כנראה פריק.

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

למשל:

N=(561)₁₀=(b1b2b3b4...)₂

כל איטרציה אתה מחשב את:

a^kmodnב- O(1)

אם אתה מקבל 1 אז אתה יכול להפסיק.

הסיבוכיות היא o(l^3) כאשר l זה מספר הביטים.

תחפש בגוגל(או בוויקי) את החישוב שרשמתי למעלה אם לא הבנת.

קוראים לזה "מבחן פרמה", ואפשר לקרוא עליו כאן http://en.wikipedia.org/wiki/Fermat_primality_test

יש מבחן יותר טוב (מבחן מילר-רבין), אבל הוא גם יותר מסובך. אפשר לקרוא עליו כאן http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

[Boomerang]

את זה חיפשתי, היכן אני יכול למצוא הוכחה מתמטית על כך?

מה שכתבתי היה ההוכחה (אפשר לכתוב את זה קצת יותר מתמטי, אבל זה נראה לי ברור)

כן! רבין-מילר! ככה קראו לו. נדמה לי שאפילו מימשנו אותו בתרגיל בהצפנה.