కౌంట్ ప్రైమ్స్ లీట్‌కోడ్ సొల్యూషన్స్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ కాపిటల్ వన్ గూగుల్ మైక్రోసాఫ్ట్
హ్యాషింగ్ మఠం

ఈ సమస్యలో, మనకు పూర్ణాంకం, N ఇవ్వబడుతుంది. N కంటే తక్కువ సంఖ్యలు ప్రైమ్‌లు ఎలా ఉన్నాయో లెక్కించడమే లక్ష్యం. పూర్ణాంకం ప్రతికూలంగా ఉండటానికి పరిమితం చేయబడింది.

ఉదాహరణ

7
3
10
4

వివరణ

10 కంటే తక్కువ ప్రైమ్‌లు 2, 3, 5 మరియు 7. కాబట్టి, కౌంట్ 4.

అప్రోచ్ (బ్రూట్ ఫోర్స్)

N కంటే తక్కువ ఉన్న ప్రతి పూర్ణాంకం కోసం తనిఖీ చేయడం మరియు అవి ప్రధానంగా ఉంటే ఫలితాన్ని పెంచడం సాధారణ విధానం. ఉదాహరణకు, N = 10 ను పరిగణించండి. ఇప్పుడు, ఈ పరిధిలో ఎన్ని ప్రైమ్‌లు ఉన్నాయో తెలుసుకోవడానికి మేము 2 నుండి N - 1 వరకు చెక్‌ను అమలు చేయవచ్చు. కానీ, ఈ విధానానికి మొత్తం పరిధిలో ప్రధాన తనిఖీ అవసరం, [2, ఎన్ - 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

కౌంట్ ప్రైమ్స్ లీట్‌కోడ్ సొల్యూషన్స్ యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

మేము కోసం ఒక లూప్ నడుపుతాము ఎన్ / 2 సార్లు. ప్రతి చెక్కులో, సంక్లిష్టత O (N / 2) సమయం (సగటున తీసుకుంటుంది ఎన్ / 2) ఖర్చు చేస్తారు. కాబట్టి, ఈ అల్గోరిథం యొక్క సమయ సంక్లిష్టత O (N√N).

స్థల సంక్లిష్టత

O (1), స్థిరమైన వేరియబుల్స్ కోసం స్థిరమైన స్థలం మాత్రమే ఉపయోగించబడుతుంది.

అప్రోచ్ (ఆప్టిమల్ మెథడ్)

ఏదైనా ప్రధాన సంఖ్యను పరిగణించండి, చెప్పనివ్వండి 5, అప్పుడు 5 యొక్క అన్ని గుణకాలు, అవి కాకుండా ప్రధానమైనవి కావు, ఎందుకంటే అవి 5 ను వారి ప్రధాన కారకాల్లో ఒకటిగా కలిగి ఉంటాయి. అదేవిధంగా, మేము అన్ని సంఖ్యలను N కన్నా తక్కువ మరియు అంతకంటే ఎక్కువ నిల్వ చేయవచ్చు 0

ది ఎరాటోస్తేనిస్ జల్లెడ N కంటే తక్కువ ప్రైమ్‌లను కనుగొనడానికి ఒక పురాతన మరియు సమర్థవంతమైన అల్గోరిథం O (N) ను కేటాయించటానికి N చిన్నది మెమరీలో స్థలం. ఇది అన్ని నాన్-ప్రైమ్ సంఖ్యలను మిశ్రమంగా గుర్తించడం ద్వారా తొలగిస్తుంది. అన్ని మిశ్రమాలను గుర్తించిన తరువాత, గుర్తు పెట్టని సంఖ్యలు ప్రైమ్‌లు.

అలాగే, మేము బూలియన్ను నిల్వ చేయాలి అమరిక మెమరీ వినియోగానికి కారణమయ్యే ఏదైనా సంఖ్య గుర్తించబడిందో లేదో తనిఖీ చేయడానికి. కాబట్టి, ఇది మనం ఉన్న సందర్భం ట్రేడ్ మెమరీ ఆఫ్ సమయానికి మెరుగుపరచండి.

కౌంట్ ప్రైమ్స్ లీట్‌కోడ్ సొల్యూషన్స్

అల్గారిథం

  1. బూలియన్ శ్రేణిని నిర్వహించండి ప్రధాన సమాన పరిమాణం ఎన్ - 1
  2. ప్రైమ్ [] మిశ్రమాలను గుర్తించడానికి మరియు చివరిలో ప్రైమ్‌లను తనిఖీ చేయడానికి ఉపయోగిస్తారు
  3. ప్రతి పూర్ణాంకం యొక్క ప్రైమ్‌ను ప్రారంభించండి నిజమైన. అల్గోరిథం సెట్ చేస్తుంది తప్పుడు ప్రతి ప్రైమ్ కాని సంఖ్యకు
  4. 2 నుండి మొదలు పూర్ణాంకం యొక్క మొదటి గుణకం వరకు వరుస పూర్ణాంకాల లూప్‌ను అమలు చేయండి N కంటే తక్కువ:
    • ప్రతి పూర్ణాంక x కోసం, ఇది ప్రైమ్ [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)). దీనిని ఇలా నిరూపించవచ్చు:

ప్రతి పూర్ణాంకం, X కోసం, మేము కొంత సమయం గడుపుతాము 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)

స్థల సంక్లిష్టత

పై), ఒక సంఖ్య ప్రధానమైనది కాదా అని నిల్వ చేయడానికి మేము హాష్ పట్టికను సృష్టిస్తాము.