પ્રીમ્સ લીટકોડ સોલ્યુશન્સ ગણતરી


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન કેપિટલ વન Google માઈક્રોસોફ્ટ
હેશિંગ મઠ

આ સમસ્યામાં, અમને પૂર્ણાંક આપવામાં આવે છે, એન. ધ્યેય એ ગણવા માટે છે કે N કરતા ઓછી સંખ્યાઓ, પ્રાઇમ કેવી છે. પૂર્ણાંક બિન-નકારાત્મક હોવાની મર્યાદા છે.

ઉદાહરણ

7
3
10
4

સમજૂતી

10 થી ઓછા પ્રાઇમ્સ 2, 3, 5 અને 7 છે. તેથી, ગણતરી 4 છે.

અભિગમ (જડ બળ)

સામાન્ય અભિગમ એ છે કે દરેક પૂર્ણાંક એન કરતા ઓછો છે અને જો તેઓ પ્રાઇમ હોય તો પરિણામમાં વધારો કરશે. ઉદાહરણ તરીકે, એન = 10 ને ધ્યાનમાં લો. હવે, આપણે આ શ્રેણીમાં કેટલા પ્રાઈમ આવેલા છે તે શોધવા માટે 2 થી N - 1 સુધી એક ચેક ચલાવી શકીએ છીએ. પરંતુ, આ અભિગમને સંપૂર્ણ શ્રેણીની મુખ્ય તપાસની જરૂર છે, [2, એન - 1].  તેથી, આ ધીમું છે.

અમે કેટલાક izપ્ટિમાઇઝેશન કરી શકીએ છીએ જેમ કે:

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

જો કે, અમારી પાસે હજી વધુ સારો અભિગમ છે, જે પછીથી આ લેખમાં ચર્ચા કરવામાં આવશે.

અલ્ગોરિધમ

  1. જો સંખ્યા ઓછી છે 3, પાછા 0, કારણ કે 2 એ સૌથી નાનો પ્રાઇમ છે
  2. 3 થી શરૂ કરીને, તમામ નંબરોની તપાસ કરતી લૂપ ચલાવો
  3. સંખ્યા, એન એ મુખ્ય છે જો:
    • તે છે 2 અને વચ્ચેના મુખ્ય પરિબળો √N
  4. જો સંખ્યા પ્રાઇમ છે, તો ઇન્ક્રીમેન્ટ પરિણામ
  5. પરિણામ છાપો

ગણતરીના પ્રીમ્સ લીટકોડ સોલ્યુશન્સનું અમલીકરણ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

જાવા પ્રોગ્રામ

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

ગણતરીના પ્રીમ્સ લીટકોડ સોલ્યુશન્સનું જટિલતા વિશ્લેષણ

સમય જટિલતા

અમે લૂપ ચલાવીએ છીએ એન / 2 વખત. દરેક તપાસમાં, જટિલતાનો સમય ઓ (એન / 2) (સરેરાશ લેતા તરીકે એન / 2) ખર્ચવામાં આવે છે. તેથી, આ અલ્ગોરિધમનો સમય જટિલતા છે ઓ (N√N)

જગ્યાની જટિલતા

ઓ (1), સતત સ્થળોનો ઉપયોગ સતત ચલો માટે થાય છે.

અભિગમ (શ્રેષ્ઠ પદ્ધતિ)

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

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

ઉપરાંત, આપણે બુલિયન સંગ્રહિત કરવાની જરૂર છે એરે કોઈપણ નંબર ચિહ્નિત થયેલ છે કે નહીં તે ચકાસવા માટે, મેમરી વપરાશ માટે કયા એકાઉન્ટ્સ છે. તેથી, આ એક કેસ છે જ્યાં આપણે વેપાર મેમરી બંધ સમય પર સુધારો.

પ્રીમ્સ લીટકોડ સોલ્યુશન્સ ગણતરી

અલ્ગોરિધમ

  1. બુલિયન એરે જાળવો વડાપ્રધાન બરાબર કદ એન - 1
  2. મુખ્ય [] કમ્પોઝિટ્સ અને ચિહ્નિત કરવા માટે વપરાય છે જે અંતમાં છે
  3. દરેક પૂર્ણાંકના મુખ્ય તરીકે પ્રારંભ કરો સાચું. અલ્ગોરિધમનો સેટ કરે છે ખોટા દરેક બિન-પ્રાઈમ નંબર પર
  4. પૂર્ણાંકોનું પ્રથમ મલ્ટીપલ ન થાય ત્યાં સુધી 2 થી શરૂ કરીને સતત પૂર્ણાંકોનો લૂપ ચલાવો N કરતા ઓછું:
    • દરેક પૂર્ણાંક x માટે, જો તેમાં પ્રાઇમ [x] સાચું હોય, તો તેના બધાને બહુવિધ તરીકે ચિહ્નિત કરો ખોટા
    • અહીં પ્રત્યેક પૂર્ણાંકનું બહુવિધ પ્રારંભ થાય છે x * x કેમ કે બીજા બધા ગુણાકાર પહેલાથી જ અંકિત થઈ જશે.
  5. છેલ્લે તપાસો કે [2, N - 1] શ્રેણીમાં કેટલી સંખ્યા છે સાચું મુખ્ય કોષ્ટકમાં
  6. પરિણામ છાપો

ગણતરીના પ્રીમ્સ લીટકોડ સોલ્યુશન્સનું અમલીકરણ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

જાવા પ્રોગ્રામ

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

ગણતરીના પ્રીમ્સ લીટકોડ સોલ્યુશન્સનું જટિલતા વિશ્લેષણ

સમય જટિલતા

એલ્ગોરિધમનો જટિલતા છે ઓ (નાલોગ (લોગએન)). આ આ પ્રમાણે સાબિત થઈ શકે છે:

દરેક પૂર્ણાંક માટે, એક્સ, અમે તેનો સમય કા .ીએ છીએ એન / એક્સ તેના બધા ગુણાકાર દૂર કરે છે.

તેથી, કુલ ખર્ચવામાં સમય છે: એન / 2 + એન / 3 + એન / 5 + એન / 7 + ……

સામાન્ય રીતે એન લેતા, ટી (એન) = એન (1/2 + 1/3 + 1/5 + 1/7 +…). શ્રેણીનો સરવાળો (1/2 + 1/3 + 1/5 + 1/7 +…) સાબિત થઈ શકે છે લોગ (લોગએન).

તેથી, ટી (એન) = નોલોગ (લોગએન)

જગ્યાની જટિલતા

ઓ (એન), જેમ કે આપણે સંગ્રહ કરવા માટે હેશ ટેબલ બનાવીએ છીએ જો નંબર પ્રાઈમ છે કે નહીં.