פורסם 2006 בינואר 1619 שנים האם לבדוק האם מהמספר 2 ועד למספר הנתון אין שארית אפס (מלבד המספר עצמו) או שיש איזה אופציה אחרת (שמספיק לבדוק עד השורש של אותו מספר נתון. מישהו שמע על זה? יש הוכחה מתמטית על כך?)
פורסם 2006 בינואר 1619 שנים אתה עושה#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>
פורסם 2006 בינואר 1619 שנים אתה יכול להפסיק בשורש, כי אם המספר X מתחלק במספר Y שגדול מהשורש שלות אז X גם מתחלק ב- (X/Y) שקטן מהשורש של X, ועליו כבר עברתיש אלגוריתם הסתברותי יותר מורכב שמגלה אם מספר הוא "כנראה" ראשוני או לא (משתמשים בו להצפנה). אבל אני לא זוכר אפילו את השם שלו וגם לא נראה לי שזה מה שאתה מחפש.
פורסם 2006 בינואר 1619 שנים קוראים לאלגו רבין קארפ משהו בסגנון מבחן פרמה התבלבלתי עם השני. אם אתה רוצה לבדוק אם N הוא ראשוני, אתה בוחר מספר רנדומאלי A בין 1 ל N. אתה בודק אם a^(n-1)mod n==1 אם כן אזי הוא ראשוני(הסתברותית) אם לא אז הוא כנראה פריק.יש אפשרות לייעל את האלגו ולהגדיל את ההסתברות להצלחה, אם אתה מחשב את החזקות לפי הביטים.למשל:N=(561)10=(b1b2b3b4...)2כל איטרציה אתה מחשב את:a^kmodnב- O(1)אם אתה מקבל 1 אז אתה יכול להפסיק.הסיבוכיות היא o(l^3) כאשר l זה מספר הביטים.תחפש בגוגל(או בוויקי) את החישוב שרשמתי למעלה אם לא הבנת.
פורסם 2006 בינואר 1619 שנים מחבר אתה יכול להפסיק בשורש, כי אם המספר X מתחלק במספר Y שגדול מהשורש שלות אז X גם מתחלק ב- (X/Y) שקטן מהשורש של X, ועליו כבר עברתאת זה חיפשתי, היכן אני יכול למצוא הוכחה מתמטית על כך?(בננה צהובה - תודה רבה על ההשקעה...)
פורסם 2006 בינואר 1619 שנים קוראים לאלגו רבין קארפ משהו בסגנון. אם אתה רוצה לבדוק אם N הוא ראשוני, אתה בוחר מספר רנדומאלי A בין 1 ל N. אתה בודק אם a^(n-1)mod n==1 אם כן אזי הוא ראשוני(הסתברותית) אם לא אז הוא כנראה פריק.יש אפשרות לייעל את האלגו ולהגדיל את ההסתברות להצלחה, אם אתה מחשב את החזקות לפי הביטים.למשל:N=(561)10=(b1b2b3b4...)2כל איטרציה אתה מחשב את: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
פורסם 2006 בינואר 1619 שנים את זה חיפשתי, היכן אני יכול למצוא הוכחה מתמטית על כך? מה שכתבתי היה ההוכחה (אפשר לכתוב את זה קצת יותר מתמטי, אבל זה נראה לי ברור) כן! רבין-מילר! ככה קראו לו. נדמה לי שאפילו מימשנו אותו בתרגיל בהצפנה.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.