שאלה אחת, יום אחד

[MegaMango]

העלאה בריבוע=העלאה ב-b

 

[yossiea]

נכון...

מה שאתה מתאר זו בדיוק הדרך שתוארה למעלה, אלא שאתה כאן מתעלם מהראשוניים, ובכן, עדיין אפשר להגיע לאותה התוצאה כיוון שאתה בודק למעשה את כל השלמים עד lg (כולל הראשוניים) אבל מה שהוצע לך זה בעצם להתעלם מכל המספרים, אין צורך לבדוק את כולם אלא רק את הראשוניים, כיוון שכל מספר שיהיה הגורם של a^b אם הוא פריק אז כל הראשוניים שמרכיבים אותו גם הם גורמים של a^b, אז אתה מגיע לתוצאה מהר יותר. וכמו שצויין מספר הראשוניים עד n הוא בערך n / ln קיבלת לדעתי קיצור דרך משמעותי לא? השאלה היא א. למה אתה מפחד מרשימת ראשוניים, ב. האם לדעתך הבדיקה או יותר נכון הערכת b על ידי כל המספרים עד lg n טובה יותר מאשר בדיקת רק הראשוניים?

 

[MegaMango]

אני מפחד ממספרים ראשוניים

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

 

[MegaMango]

yossiea פתר את זה לפני שעה שש!

*מעניק לyossiea אגוז*

 

[vinney]

זה אומר שהתנדבת

לשלוח שאלה יומית כל יום בשש בערב ?

 

[MegaMango]

קודם נסיים עם השירשור חידות P:

 

[ron369]

נראה לי שהוא מיצה את עצמו

עוד חידה!