പ്രൈമുകളുടെ എണ്ണം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ക്യാപിറ്റൽ വൺ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
ഹാഷിംഗ് മഠം

ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾ‌ക്ക് ഒരു സംഖ്യ നൽകിയിരിക്കുന്നു. N നെക്കാൾ കുറവുള്ള സംഖ്യകൾ പ്രൈമുകളാണെന്ന് കണക്കാക്കുകയാണ് ലക്ഷ്യം. സംഖ്യ നെഗറ്റീവ് അല്ലാത്തതായി പരിമിതപ്പെടുത്തിയിരിക്കുന്നു.

ഉദാഹരണം

7
3
10
4

വിശദീകരണം

10 ൽ താഴെയുള്ള പ്രൈമുകൾ 2, 3, 5, 7 എന്നിവയാണ്. അതിനാൽ, എണ്ണം 4 ആണ്.

സമീപനം (ബ്രൂട്ട് ഫോഴ്സ്)

N- നേക്കാൾ കുറവുള്ള ഓരോ സംഖ്യയും പരിശോധിച്ച് അവ പ്രൈം ആണെങ്കിൽ ഫലം വർദ്ധിപ്പിക്കുക എന്നതാണ് പൊതുവായ സമീപനം. ഉദാഹരണത്തിന്, N = 10 പരിഗണിക്കുക. ഇപ്പോൾ, ഈ ശ്രേണിയിൽ എത്ര പ്രൈമുകൾ കിടക്കുന്നുവെന്ന് കണ്ടെത്താൻ നമുക്ക് 2 മുതൽ N - 1 വരെ ഒരു പരിശോധന നടത്താം. പക്ഷേ, ഈ സമീപനത്തിന് മുഴുവൻ ശ്രേണിയിലും ഒരു പ്രധാന പരിശോധന ആവശ്യമാണ്, [2, N - 1].  അതിനാൽ, ഇത് മന്ദഗതിയിലാണ്.

ഇനിപ്പറയുന്നതുപോലുള്ള ചില ഒപ്റ്റിമൈസേഷനുകൾ ഞങ്ങൾക്ക് ചെയ്യാൻ കഴിയും:

  1. 2 ഒഴികെയുള്ള എല്ലാ പ്രൈം നമ്പറുകളും വിചിത്ര സംഖ്യയാണ്. അതിനാൽ, ശേഷം 2, വിചിത്ര സംഖ്യകൾക്കായി മാത്രമേ ഞങ്ങൾക്ക് പരിശോധിക്കാൻ കഴിയൂ.
  2. ഒരു നമ്പർ പ്രൈം ഇൻ ആണോ എന്ന് ഞങ്ങൾക്ക് പരിശോധിക്കാം O (√N) അൽഗോരിതം മെച്ചപ്പെടുത്താനുള്ള സമയം.

എന്നിരുന്നാലും, ഞങ്ങൾക്ക് ഇപ്പോഴും ഒരു മികച്ച സമീപനമുണ്ട്, ഈ ലേഖനത്തിൽ പിന്നീട് ചർച്ചചെയ്തു.

അൽഗോരിതം

  1. സംഖ്യ കുറവാണെങ്കിൽ 3, മടങ്ങുക 0, 2 എന്നത് ഏറ്റവും ചെറിയ പ്രൈം ആണ്
  2. 3 മുതൽ എല്ലാ അക്കങ്ങളും പരിശോധിച്ച് ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
  3. ഒരു സംഖ്യ, N പ്രധാനമാണെങ്കിൽ:
    • അതുണ്ട് 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

കൗണ്ട് പ്രൈമുകളുടെ സങ്കീർണ്ണ വിശകലനം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ

സമയ സങ്കീർണ്ണത

ഞങ്ങൾ ഇതിനായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുന്നു N / 2 തവണ. എല്ലാ പരിശോധനയിലും, സങ്കീർണ്ണതയുടെ സമയം O (N / 2) (ശരാശരി കണക്കാക്കുന്നു N / 2) ചെലവഴിച്ചു. അതിനാൽ, ഈ അൽഗോരിത്തിന്റെ സമയ സങ്കീർണ്ണതയാണ് O (N√N).

സ്ഥല സങ്കീർണ്ണത

O (1), സ്ഥിരമായ വേരിയബിളുകൾക്കായി സ്ഥിരമായ ഇടം മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ.

സമീപനം (ഒപ്റ്റിമൽ രീതി)

ഏതെങ്കിലും പ്രൈം നമ്പർ പരിഗണിക്കുക, പറയട്ടെ 5, 5 ഒഴികെയുള്ള എല്ലാ ഗുണിതങ്ങളും ഒരിക്കലും പ്രൈം ആകാൻ കഴിയില്ലെന്ന് ഉറപ്പാണ്, കാരണം അവയുടെ പ്രധാന ഘടകങ്ങളിലൊന്നായി 5 ഉണ്ടായിരിക്കും. അതുപോലെ, നമുക്ക് N- നേക്കാൾ വലുതും വലുതുമായ എല്ലാ അക്കങ്ങളും സംഭരിക്കാൻ കഴിയും 0

ദി എറാട്ടോസ്റ്റെനെസ് അരിപ്പ N നേക്കാൾ കുറഞ്ഞ പ്രൈമുകൾ കണ്ടെത്താനുള്ള പുരാതനവും കാര്യക്ഷമവുമായ അൽഗോരിതം ആണ് O (N) അനുവദിക്കുന്നതിന് N ചെറുതാണ് മെമ്മറിയിൽ ഇടം. പ്രൈം ഇതര സംഖ്യകളെ സംയോജിതമെന്ന് അടയാളപ്പെടുത്തി ഇത് ആവർത്തനമായി ഇല്ലാതാക്കുന്നു. എല്ലാ മിശ്രിതങ്ങളും അടയാളപ്പെടുത്തിയ ശേഷം, അടയാളപ്പെടുത്താത്ത അക്കങ്ങൾ പ്രൈമുകളാണ്.

കൂടാതെ, ഞങ്ങൾ ഒരു ബൂളിയൻ സംഭരിക്കേണ്ടതുണ്ട് ശ്രേണി മെമ്മറി ഉപയോഗത്തിന് കാരണമാകുന്ന ഏതെങ്കിലും നമ്പർ അടയാളപ്പെടുത്തിയിട്ടുണ്ടോ ഇല്ലയോ എന്ന് പരിശോധിക്കാൻ. അതിനാൽ, ഇത് ഞങ്ങൾ ഒരു സാഹചര്യമാണ് ട്രേഡ് മെമ്മറി ഓഫ് കൃത്യസമയത്ത് മെച്ചപ്പെടുത്തുക.

പ്രൈമുകളുടെ എണ്ണം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ

അൽഗോരിതം

  1. ഒരു ബൂളിയൻ അറേ നിലനിർത്തുക പ്രൈം വലുപ്പത്തിന് തുല്യമാണ് N - 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

കൗണ്ട് പ്രൈമുകളുടെ സങ്കീർണ്ണ വിശകലനം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ

സമയ സങ്കീർണ്ണത

അൽഗോരിത്തിന്റെ സങ്കീർണ്ണതയാണ് O (Nlog (logN)). ഇത് ഇതായി തെളിയിക്കാം:

ഓരോ സംഖ്യയ്ക്കും, എക്സ്, ഞങ്ങൾ ഒരു സമയം ചെലവഴിക്കുന്നു N / X. അതിന്റെ ഗുണിതങ്ങളെ ഇല്ലാതാക്കുന്നു.

അതിനാൽ, ആകെ ചെലവഴിച്ച സമയം: N / 2 + N / 3 + N / 5 + N / 7 + ……

N സാധാരണപോലെ എടുക്കുന്നു, ടി (എൻ) = എൻ (1/2 + 1/3 + 1/5 + 1/7 +…). സീരീസ് തുക (1/2 + 1/3 + 1/5 + 1/7 +…) എന്ന് തെളിയിക്കാനാകും ലോഗ് (ലോഗ് എൻ).

അതുകൊണ്ടു, T (N) = Nlog (logN)

സ്ഥല സങ്കീർണ്ണത

O (N), ഒരു സംഖ്യ പ്രധാനമാണോ അല്ലയോ എന്ന് സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു ഹാഷ് പട്ടിക സൃഷ്ടിക്കുന്നതിനാൽ.