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

[iakovl]

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

[BoRIS]

אוקיי, קודם כל מה זה מספר ראשוני?

זה מספר שמתחלק רק בעצמו וב-1.

עכשיו, איך בודקים שהמספר הוא מספר ראשוני?

בודקים אם הוא מתחלק באחד מהמספרים החל ב-2 ועד החצי של המספר (אם הוא אי-זוגי, תחסר ממנו 1, חלק ב-2, ואז חבר אל התוצאה 1).

במידה והמספר מתחלק באחד המספרים הללו, הוא איננו ראשוני.

[captaincaveman]

אוקיי, קודם כל מה זה מספר ראשוני?

זה מספר שמתחלק רק בעצמו וב-1.

עכשיו, איך בודקים שהמספר הוא מספר ראשוני?

בודקים אם הוא מתחלק באחד מהמספרים החל ב-2 ועד החצי של המספר (אם הוא אי-זוגי, תחסר ממנו 1, חלק ב-2, ואז חבר אל התוצאה 1).

במידה והמספר מתחלק באחד המספרים הללו, הוא איננו ראשוני.

מספיק לבדוק עד השורש של המספר.

[BoRIS]

מספיק לבדוק עד השורש של המספר.

וואלה צודק!

[ooopsi]

זה בשביל ביה"ס או יותר רציני/כיף ?

[toxigun]

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

j=0
k=2

while j < n 
{
  flag = true
  for  i = 0 to j - 1
    if array[i] divides k then flag = false

  if flag=true then
  {
    add k to array
    j = j + 1
  }
  k = k + 1
}

[toxigun]

בתום התהליך המערך יכיל n מספרים ראשוניים.

[slider]

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

[Holy]

יש אלגוריתם שעושה את זה הרבה יותר מהר אם אתה מחפש את כל המספרים הראשוניים מ-0 עד מקום מוסיים ידוע מראש

הרעיון הוא להגדיר מארך שכל איבר בו מקבך 0 או 1 (bit אחד) בגודל של המספר הידוע מראש (מאותחל לאפסים)

אתה מתחיל מ-2

משאיר את הסימון כ-0 (כלומר 2 ראשוני) ועבור כל הכפולות של 2 אתה מסמן 1

עובד לאיבר הבא שלא מסומן כלומר לאיבר 3 ומסמן את כל הכפלות שלו

עובד לאיבר הבא שלא מסומן כלומר 5 (4 סומן כבר) ומסמן את כל הכפולות שלו

וכו....

קוד שעכשיו כתבתי ולא ממש בדקתי באגים

למצוא את כל המספרים בין 1 ל-999

#define N 1000

int a[N] = {0};

int i,j;

for(i=2;i<N;i++)

{

if(a == 1) continue;

for(j=i+i;j<N;j+=i) a[j] = 1;

}

בסיום כל האיברים שהם 0 הם ראשוניים וכל אלה שהם 1 הם לא ראשוניים

אם זה מעניין אותך

סיבוכיות זמן O(n)

סיבוכיות מקום O(n)

האלגוריתם השניע שהציעו לך הוא בסיבוכיות

זמן O(n^(3/2))

מקום O(1)

[toxigun]

הנה מימוש של האלגוריתם שאני הצעתי, עם שיפוץ נחמד.

הקוד מייצר את num המספרים הראשוניים ושומר אותם במערך array.

האלגוריתם של holy נחמד מאוד... לא ניסיתי אותו מול שלי מבחינת מהירות, אבל מבחינת מקום הוא הרבה יותר בזבזני. (מה שרומז שהוא יותר מהיר :-)).

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

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

[Holy]

וזה בדיוק מה שרשום בהודעה שלי....

גם שלי יכול למצוא את n הראשוניים עם הקצאה דינמית אבל אני לא אכנס לזה

[toxigun]

סיבוכיות זמן O(n)

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

בניגוד למה שכתבת, האלגוריתם שלי הוא בעל סיבוכיות של

e(sqrt(n))

כאשר e(x) היא הפונקציה של אוילר (מחזירה את מספר הכופלים הראשוניים של x).

[Holy]

אתה צודק ששלי לא O(n)

אבל שלך כן O(n*sqrt(n))

כש-n הוא הערך של המספר הראשוני הכי גבוה שמצאת

[toxigun]

אתה צודק ששלי לא O(n)

אבל שלך כן O(n*sqrt(n))

אם כבר אז:

O[ n*e(sqrt n) ]

שזה הרבה יותר נמוך מ:

O(n*sqrt(n))

יש הרבה פחות ראשוניים עד השורש של n מאשר סה"כ המספרים עד השורש של n.

[Holy]

אבל אתה עובר מספר מספר ובודק את כל המספרים ממנו עד השורש שלו

זה n*sqrt(n