אני לא... אני בודק את כל ה*ראשוניים* עד השורש שלו.

תסתכל טוב על המימוש שלי:

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++;
  }
}

מישהו יכול לתרגם את האלגוריתמים האלו לפסקל? זה מעניין אותי.

חיובי 8)

procedure gen_primes(var arr: array of longint; num: integer);
var
  number, sqr: longint;
  i,cnt: integer;
  flag: boolean;
begin
  number := 2;
  cnt := 0;
  while cnt < num do
  begin
    sqr:=longint(sqrt(number)+1);
    i:=0;
    while (i<cnt-1) and (arr[i]<sqr) and flag do
    begin
      if (number mod arr[i]) = 0 then flag := false;
      i := i + 1;
    end;
    if flag then
    begin
      arr[cnt]:=number;
      cnt := cnt + 1;
    end;
    number := number + 1;
  end;
end;

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

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

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

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

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

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

ראשוניים?

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

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

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

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

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

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

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

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

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

O(n * e(n))

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

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

טוב, נתחיל מזה שהאלגוריתם שנתתי ע"מ לבדוק האם מס' הוא ראשוני או לא, פועל ב(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 ראשוניים.

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

אתה מוזמן לממש את שלך ולבנות גראף של זמן הריצה כפונקציה של הראשוני ה-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;
}

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

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'. אך גם בדיקה זו, בסופו של דבר תיכשל.

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

כן, כן, אני התבלבלתי פה, מה שכתבתי מחזיר TRUE אם המס' הוא לא ראשוני, ו FALSE אחרת..

אני אערוך את זה בעוד שניה...

בעניין שאר הדברים, ישנם מספרים שנקראים מספרי Carmichael, שעצם הגדרתם היא שהם מכשילים את האלגוריתם הזה (1729 הוא מס' כזה למיטב זכרוני, וכך גם 561 למשל), וזה לא קשור כלל להיותו אלגוריתם הסתברותי.

מה שכן, ישנו משפט אחר, שאומר שמס' N הוא ראשוני אם"ם עבור כל( A < 2*Log(N

(2/(A^((N-1 =(מודולו N) סימן לג'נדר של A לפי N

וכך אפשר לכתוב אלגוריתם שפועל תמיד, וסיבוכיותו היא( LOG^3(N.

בעניין קביעתך שיצירת ראשוניים ע"י בדיקת ראשוניות היא לעולם יותר איטית, זה פשוט לא נכון!

וזאת משום שבדיקת הראשוניות שלך, למרות שהיא משתמשת במס' ראשוניים שכבר יוצרו, עדיין לוקחת(((O(pi(sqrt(N וזה שקול ל

((O((sqrt(N)/LN(sqrt(N. ולכן זה הרבה יותר איטי מהאלגורימים שאני הצעתי, ולא בהרבה יותר טוב מהאלגוריתם הכי טריביאלי...

לא הרבה יותר מהיר מהאלגוריתם הטריויאלי? אני לא יודע מה אומרים לך מדעי המחשב התאורטיים, אבל מדידה מעשית של זמני ריצה אומרת לי את הדבר הבא:

אלגוריתם שאני הצעתי:

האלגוריתם הטריויאלי עם בדיקת ראשוניות שבודקת התחלקות עד השורש:

הגרפים אמורים להיות כפונק' של N, לא של הראשוני ה - N !

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

ברור לי שבפועל זה פועל יותר מהר, אבל לא בסדר גודל יותר מהר.

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

ניסיתי. משום מה זה רק איטי יותר. כנראה עניין של instruction scheduling או משהן. או יכול להיות שפקודות inc עובדות יותר מהר מפקודות add.

אתה לא ממש יכול להשוות ככה ביצועים

המחשב שלך לא נמצא בדיוק באותו מצב כשהרצת את שני התוכניות

מצב אחר של הזיכרון

אירגון אחר של הדפים הוירטואלים

החלפת תהליכים

ישמוים אחרים שרצים לך ברקע

פסיקות שלא קשורות לתוכנה שלך

ועוד עשרות דברים יכולים להשפיע על התוצאה