ספירת ראשונים בטווחים


רמת קושי בינוני
נשאל לעתים קרובות Google טיול קוליזה לְנַפּוֹת Snapchat יאהו
מתמטיקה מערכת מספר

הצהרת בעיה

הבעיה "ספירת ראשונים בטווחים" קובעת שקיבלת טווח [שמאל, ימין], שם 0 <= שמאל <= ימינה <= 10000. הצהרת הבעיה מבקשת לברר את המספר הכולל של המספרים הראשוניים בטווח. בהנחה שיהיו מספר רב של שאילתות.

דוגמה

left: 4
right:10
2

הסבר

5 ו- 7 הם שני המספרים הראשוניים היחידים.

ספירת ראשונים בטווחים

left: 6
right:8
1

הסבר

7 הוא המספר העיקרי היחיד.

אַלגוֹרִיתְם

  1. צור מספר שלם מערך ומערך בוליאני 'רִאשׁוֹנִי' בגודל המרבי הנתון ואותחל את המערך הבוליאני באמצעות נכון.
  2. חצו את המערך הבוליאני ובדקו אם הערך הנוכחי של מערך 'פריים' נכון.
  3. ואז התחל לעבור מאלמנט המערך הנוכחי ואתחל כל אלמנט מערך מכאן ואילך לשקר שנמצא במרחק השווה לגודל האלמנט הנוכחי. זה אומר שאנחנו עוברים לכפולות של האלמנט הנוכחי.
  4. הגדר את prePrime [0] ו- prePrime [1] ל- 0.
  5. חצה מה -2 עד הערך המרבי הנתון.
  6. העתק את הערך לאינדקס הקודם של מערך prePrime ובדוק אם הערך הנוכחי של המערך הראשי שווה ל- true, ואז הגדל את ערך הערך prePrime ב -1.
  7. עבור כל שאילתה החזירו את ההפרש בין prePrime [right] ו- prePrime [left-1].

הסבר

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

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

הגדרנו את הערך 0th ו 1st ערך של prePrime מערך ל 0. כך שנתחיל מ 2 לחצות את מערך prePrime ו prime. לאחר מכן אנו מעתיקים את הערך הבא של מערך prePrime לערך הקודם של מערך prePrime ונבדוק אם הערך הנוכחי של המערך הראשי נכון, אם נכון אז הגדל את ערך האלמנט הנוכחי של מערך prePrime. עבור כל שאילתה נקבל כמספר התחלתי ומספר סיום. נחזיר את ההפרש בין prePrime [ימין] ו- prePrime [שמאל -1]. זו תהיה התשובה הנדרשת.

קופונים

יישום ב- C ++ לספירת ראשוניים בטווחים

#include<iostream>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MAX = 10000;

int prePrime[MAX + 1];

void PrePrimeFunction ()
{

    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));

    for (int a = 2; a * a <= MAX; a ++)
    {
        if (prime[a] == true)
        {
            for (int i = a * 2; i <= MAX; i += a)
                prime[i] = false;
        }
    }
    prePrime[0] = prePrime[1] = 0;
    for (int q = 2; q <= MAX; q++)
    {
        prePrime[q] = prePrime[q - 1];
        if (prime[q])
            prePrime[q]++;
    }
}

int solveQuery(int L, int R)
{
    return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
}

int main()
{
    PrePrimeFunction();

    int L = 4, R = 10;
    cout << solveQuery(L, R) << endl;

    L = 6, R = 8;
    cout << solveQuery(L, R) << endl;

    return 0;
}
2
1

יישום ב- Java לספירת ראשוניים בטווחים

import java.util.Arrays;

class PrimeInRange
{

    static final int MAX = 10000;

    static int prePrime[] = new int[MAX + 1];

    static void PrePrimeFunction()
    {

        boolean prime[] = new boolean[MAX + 1];
        Arrays.fill(prime, true);

        for (int a = 2; a * a <= MAX; a++)
        {
            if (prime[a] == true)
            {

                for (int i = a * 2; i <= MAX; i += a)
                    prime[i] = false;
            }
        }

        prePrime[0] = prePrime[1] = 0;

        for (int q = 2; q <= MAX; q++)
        {
            prePrime[q] = prePrime[q - 1];
            if (prime[q])
                prePrime[q]++;
        }
    }

    static int solveQuery(int L, int R)
    {
        return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
    }

    public static void main(String[] args)
    {
        PrePrimeFunction();
        int L = 4, R = 10;
        System.out.println(solveQuery(L, R));

        L = 6;
        R = 8;
        System.out.println(solveQuery(L, R));
    }
}
2
1

ניתוח מורכבות

מורכבות זמן

O (n * log (log (n)) + q) איפה "N" הוא מספר האלמנטים במערך ו- "Q" הוא מספר השאילתות. לפיכך מורכבות הזמן הזו היא בגלל האלגוריתם שהשתמשנו בו "מסננת של ארטוסטנס".

מורכבות בחלל

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