રેન્જમાં પ્રાઇમ્સની ગણતરી કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે Google પર્યટન કુલીઝા ચાળણી Snapchat યાહૂ
મઠ સંખ્યા સિસ્ટમ

સમસ્યા નિવેદન

"રેન્જમાં પ્રાઇમ ગણતરી" સમસ્યા જણાવે છે કે તમને શ્રેણી [ડાબે, જમણે] આપવામાં આવે છે, જ્યાં 0 <= ડાબી <= અધિકાર <= 10000. સમસ્યાનું નિવેદન શ્રેણીની અંદરના મુખ્ય સંખ્યાઓની કુલ સંખ્યા શોધવા માટે પૂછે છે. ધારી રહ્યા છીએ કે ત્યાં મોટી સંખ્યામાં પ્રશ્નો હશે.

ઉદાહરણ

left: 4
right:10
2

સમજૂતી

5 અને 7 ફક્ત 2 મુખ્ય સંખ્યા છે.

રેન્જમાં પ્રાઇમ્સની ગણતરી કરો

left: 6
right:8
1

સમજૂતી

7 એ એકમાત્ર મુખ્ય સંખ્યા છે.

અલ્ગોરિધમ

  1. બનાવો પૂર્ણાંક એરે અને બુલિયન એરે 'પ્રાઇમ' મહત્તમ આપેલ કદ અને બુલિયન એરે સાથે પ્રારંભ કરો સાચું.
  2. બુલિયન એરેને પસાર કરો અને તપાસો કે 'પ્રાઈમ' એરેનું વર્તમાન મૂલ્ય સાચું છે કે નહીં.
  3. પછી વર્તમાન એરે એલિમેન્ટમાંથી પસાર થવાનું શરૂ કરો અને ત્યારબાદ ખોટા તરફના દરેક એરે એલિમેન્ટને પ્રારંભ કરો જે વર્તમાન તત્વની પરિમાણ સાથે સમાન અંતરે છે. આનો અર્થ એ છે કે આપણે વર્તમાન તત્વના ગુણાંકમાં આગળ વધી રહ્યા છીએ.
  4. પ્રીપ્રાઇમ [0] અને પ્રિપ્રાઇમ [1] થી 0 સેટ કરો.
  5. મહત્તમ આપેલ મૂલ્ય સુધી 2 થી પસાર થવું.
  6. પ્રીપ્રાઇમ એરેના પહેલાના અનુક્રમણિકામાં મૂલ્યની ક Copyપિ કરો અને તપાસો કે પ્રાઇમ એરેનું વર્તમાન મૂલ્ય સાચું છે કે નહીં, તો પ્રિપ્રાઇમના મૂલ્યનું મૂલ્ય 1 દ્વારા વધારવું.
  7. દરેક ક્વેરી માટે પ્રિપ્રાઇમ [જમણે] અને પ્રીપ્રાઇમ [ડાબી -1] નો તફાવત પાછો ફરો.

સમજૂતી

પ્રારંભિક સંખ્યા અને અંતિમ સંખ્યા તરીકે સંખ્યાની શ્રેણી આપવામાં. આમ આ શ્રેણીને ધ્યાનમાં લેવી કારણ કે તે બધી અંદરની સંખ્યાઓથી ભરેલી છે. અમે આ શ્રેણીમાં મુખ્ય સંખ્યાઓની કુલ સંખ્યા શોધવા માટે કહ્યું છે. આ માટે, અમે પ્રીપ્રાઇમ એરે બનાવીશું, જેના દ્વારા આપણે મહત્તમ સંખ્યાની શ્રેણીમાં કોઈપણ ક્વેરીને હલ કરી શકીએ. અમને આપેલ 10000 ની મહત્તમ કદની પૂર્ણાંક એરે જાહેર કરો, અને તે જ કદ સાથે, અમે બુલિયન એરે જાહેર કરીશું, જેમાંથી આપણે મૂલ્યને સાચું તરીકે પ્રારંભ કર્યું.

મૂલ્ય બેમાંથી લૂપમાં પસાર થવું કારણ કે આપણે કોઈને અગ્રિમ નંબર તરીકે ગણી શકતા નથી. બુલિયન પ્રાઈમ એરેની દરેક સંખ્યા તપાસો કે દરેક મૂલ્ય બરાબર છે, જો તે સાચું હોવાનું જણાયું છે, તો આપણે આગળ લૂપમાં આગળ નીકળીશું. અમે વર્તમાન સંખ્યાના બમણા ભાગથી પ્રારંભ કરીશું અને મહત્તમ કદની કિંમત સુધી પહોંચવા સુધી તેના ગુણાકાર તરફ આગળ વધીશું અને ત્યારબાદથી ખોટી તરફ દરેક મૂલ્યની શરૂઆત કરીશું. આ અભિગમને સામાન્ય રીતે તરીકે ઓળખવામાં આવે છે ઇરાટોસ્થેન્સની ચાળણી.

આપણે 0 ની કિંમત નક્કી કરીth અને 1st પ્રીપ્રાઇમ એરે ની વેલ્યુ 0 થી. જેથી આપણે 2 થી પ્રારંભ કરીશું અને પ્રીપ્રાઇમ અને પ્રાઇમ એરે પસાર કરીશું. તો પછી આપણે પ્રિપ્રાઇમ એરેના આગલા મૂલ્યને પ્રીપ્રાઇમ એરેના પહેલાના મૂલ્યમાં ક copyપિ કરીએ છીએ અને તપાસ કરીએ છીએ કે પ્રાઇમ એરેનું વર્તમાન મૂલ્ય સાચું છે કે નહીં, જો સાચું હોય તો પ્રિપ્રાઇમ એરેના વર્તમાન ઘટકનું મૂલ્ય વધારવું. દરેક ક્વેરી માટે આપણે પ્રારંભિક નંબર અને અંતિમ નંબર તરીકે પ્રાપ્ત કરીશું. અમે પ્રીપ્રાઇમ [જમણે] અને પ્રીપ્રાઇમ [ડાબી -1] નો તફાવત પાછા આપીશું. તે જરૂરી જવાબ હશે.

કોડ

રેન્જમાં પ્રાઈમ ગણવા માટે સી ++ માં અમલીકરણ

#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

રેન્જમાં પ્રાઈમ ગણવા માટે જાવામાં અમલીકરણ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * લ logગ (લોગ (એન)) + ક્યૂ) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે અને "ક્યૂ" પ્રશ્નોની સંખ્યા છે. આમ આ વખતે જટિલતા એ છે કે આપણે "ratરેટોસ્થેનીસની ચાળણી" નો ઉપયોગ એલ્ગોરિધમનો કારણે કર્યો છે.

અવકાશ જટિલતા

ઓ (1) કારણ કે એરેનું કદ ઇનપુટ પર આધારિત નથી, તે સતત મૂલ્ય સમાન છે. કારણ કે પ્રાઈમ્સના પરિણામને સંગ્રહિત કરવા માટે જગ્યા આવશ્યક છે. કારણ કે આપણે સંગ્રહ કરીએ છીએ જો સંખ્યા પ્રાઇમ છે કે નહીં.