מספרים ראשוניים ב visual c++

- Share

טוב, הנה אלגוריתם(בפסאודו-קוד) שבהנתן מס' בודק האם הוא ראשוני. יש לציין שזהו אלגוריתם הסתברותי...

Prime?(n)

for i = 0 to C

begin

a = random number between 2 and n

if a ^ n <> a mod n then

return true

end

return false

קישור לתוכן

שתף באתרים אחרים

slider

- Share

זה ההמשך של ההודעה הקודמת...

C הנו קבוע שלמעשה קובע את ההסתברות שהאלגוריתם יפעל שהיא 0.5 בחזקת C . במילים אחרות, אם לבחור C = 400 למשל, הסיכוי שהאלגוריתם לא יפעל היא נמוכה שהמחשב יעשה טעות בחיבור מספרים כתוצאה מקרינה קוסמית שמגיעה מהחלל (ככה אמר המרצה שלי באוניברסיטה...).

האלגוריתם הזה בודק למעשה ראשוניות של מס מסוים ב O(1) זמן!

עכשיו מכאן ועד למצוא N ראשוניים ב O(N) הדרך ברורה. מה שכן, נדמה לי שאפשר חעשות את זה בפחות, בזכות משפט מתורת המספרים שאומר שעבו N גדול, מס' ראשוני מופיע בערך כל ln(N) ... אולי אני אכתוב אותו אם אני אמצא את זה...

קישור לתוכן

שתף באתרים אחרים

toxigun

- Share

ראשוניים?

ראשוניים בהסתברות מסויימת.

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

האלגוריתמים שלי ושל holy מוגדרים בצורה אינדוקטיבית, ופועלים בסיבוכיות יחסית נמוכה. קיים פרט נוסף שצריך לשים לב אליו:

f(x)=O(g(x))

גורר שמתקיים:

lim [f(x)/g(x)] = c

כאשר x שואף לאינסוף ו-C הוא מספר קבוע. כאשר הקבוע הוא גבוהה מאוד, האלגוריתם למרות סיבוכיותו הנמוכה מפסיק להיות יעיל. זה בדיוק מה שקורה במקרה שלך.

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

בנוסף, ניתן להוכיח מתמטית שלא ניתן לייצר n מספרים ראשוניים בסיבוכיות זמן נמוכה יותר מ:

O(n * e(n))

כאשר e(n)=a היא הפונקציה של אוילר, שמחזירה את כמות המחלקים הראשוניים של n.

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

קישור לתוכן

שתף באתרים אחרים

slider

- Share

טוב, נתחיל מזה שהאלגוריתם שנתתי ע"מ לבדוק האם מס' הוא ראשוני או לא, פועל ב(O(ln(n , משום בחישוב של a^n mod n לוקח O(ln(n) . וההסתברות שהאלגוריתם היא גבוהה עד כדי כך, שיש פחות סבירות שהוא יטעה מאשר הסבירות שהמחשב יעשה טעות חישוב! (כמו שכבר ציינתי).

כתוצאה מכך, אפשר בקלות למצוא n מס' ראשוניים ב((O(n*ln^2(n,

פשוט ע"י ריצה על כל המספרים ובדיקת ראשוניות שלהם עד שנגיע ל N ראשוניים, מה שיקרה בקירוב במס' ע N*ln(N) .

[למעשה זוהי הגזמה שכן, הראשוני ה N הוא בקירוב N*ln(N)]

כעת, אני לא יודע איך הגעת למסקנה שסיבוכיות זמן הריצה של האלגוריתם שנתת היא((O(n*e(n אבל זה פשוט לא נכון!

קודם כל, הראשוני ה N-י הוא, כמו שאמרתי, בקירוב(N*ln(N , כעת עבור כל cnt, אתה בודק האם הוא מתחלק בראשוניים עד ל sqrt(cnt)

ויש((pi(sqrt(cnt , כאלה. ולכן סיבוכיות זמן הריצה היא סכום על כל ה m ים מ 2 עד(N*ln(N של((pi(sqrt(m.

כעת הדבר הזה הוא מאוד קשה לחישוב גם לאחד שלמד קורס כמו תורת המספרים שאוניברסיטה (כמוני (קיבלתי 95)), אבל בקירוב, הסכום הזה שווה ל ((O(N^1.5*ln(N . ככה שזה לא הרבה יותר טוב מהשיטה הכי טריביאלית למציאת N ראשוניים.

קישור לתוכן

שתף באתרים אחרים

toxigun

- Share

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

אתה מוזמן לממש את שלך ולבנות גראף של זמן הריצה כפונקציה של הראשוני ה-Nי. זה מה שאני עשיתי, ובאופן מעשי האלגוריתם שלי רץ בזמן כמעט לינארי, למרות שהסיבוכיות שלו לא קרובה ללהיות לינארית.

הנה תוכנית מלאה שמממשת את שלי ואפילו מודדת זמן:


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define INP_ERROR "Input error."
#define MEM_ERROR "Memory allocation error."

typedef enum {FALSE,TRUE} boolean;

void gen_primes(int num, long array[])
{
  long number=2, sqr;
  int i,cnt=0;
  boolean flag;
  while (cnt < num) {
    sqr=(long) sqrt(number) + 1;
    flag=TRUE;
    /* check if number is divisible by
       primes that come before it */
    for(i=0;(i<cnt-1) && (array[i]<sqr) && flag;i++) {
      if (number%array[i]==0) {
        flag=FALSE;
      }
    }
    if (flag) {
      array[cnt++]=number;
    }
    number++;
  }
}

int save_primes(long primes[], int count, char *file)
{
  FILE *f;
  int i;

  /* create "file" for writing */
  f=fopen(file,"w+");
  /* if fopen failed, print error and exit with failure */
  if(NULL==f) {
    printf("\nUnable to open %s for writing.\n",file);
    return 1;
  }

  /* save primes to the file. */
  for(i=0;i<count;i++) {
    /* if fprintf failed to write a prime print error and
       exit function with failure */
    if(EOF==fprintf(f,"%ld\n",primes[i])) {
      printf("\nError writing primes to %s.\n",file);
      fclose(f);
      return 1;
    }
  }

  /* close the file and return with success */
  fclose(f);
  return 0;
}

int main(int argc, char *argv[])
{
  int num;
  long *primes;
  clock_t tm;
  double dtm;

  printf("How many primes do you want to generate?\n");
  if (scanf("%d",&num)!=1) {
    fputs(INP_ERROR,stderr);
    exit(EXIT_FAILURE);
  }

  if(NULL==(primes=(long *)malloc(sizeof(long)*num))) {
    fputs(MEM_ERROR,stderr);
    exit(EXIT_FAILURE);
  }

  printf("Generating primes...");
  tm=clock();
  gen_primes(num, primes);
  tm=clock()-tm;
  printf("done.\n");

  dtm=tm/(double) CLOCKS_PER_SEC;
  printf("Generation took %.2f seconds.\n",dtm);
  printf("The last prime is %ld\n",primes[num-1]);

  if(argc>1) {
    printf("Saving primes to %s...",argv[1]);
    if(!save_primes(primes,num,argv[1])) {
      printf("done.\n");
    }
  }

  free(primes);
  return 0;
}

קישור לתוכן

שתף באתרים אחרים

toxigun

- Share

טוב, הנה אלגוריתם(בפסאודו-קוד) שבהנתן מס' בודק האם הוא ראשוני. יש לציין שזהו אלגוריתם הסתברותי...
Prime?(n)
for i = 0 to C
begin
a = random number between 2 and n
if a ^ n <> a mod n then
return true
end
return false

הממ... אתה בטוח שזה עובד בכלל?

לדוגמא, נקח את 4, שהוא לא ראשוני. למיטב ידיעתי, 3 בחזקת 4 לא שווה לשארית החלוקה של 3 ב4-.

קיימות בדיקות הסתברותיות הרבה יותר טובות. לדוגמא: לבדוק האם שארית החלוקה של a בחזקת n-1 ב-n שונה מ1- עבור כל איטרציה של הלולאה שהצעת. אבל גם בדיקה זו תיכשל. לדוגמא, עבור המספר 1729 (לא ראשוני) היא תקבע שהיא לא הצליחה להפריך את ראשוניותו, אבל למרות זאת המספר הוא לא ראשוני.

קיימת בדיקת ראשוניות נוספת, שעובדת בהסתברות הרבה יותר גבוהה, וקוראים לה 'the strong pseudoprimality test'. אך גם בדיקה זו, בסופו של דבר תיכשל.

בדיקת ראשוניותו של מספר היא בעיה עם פתרונות רבים. אבל יצירת סדרה של מספרים ראשוניים באמצעות בדיקות ראשוניות רגילות בד"כ תעבוד לאט יותר מאשר יצירה באמצעות אלגוריתם אינדוקטיבי שמשתמש במה שכבר נוצר.

קישור לתוכן

שתף באתרים אחרים

slider

- Share