प्राइमहरूको लेटकोड समाधानहरू गणना गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन एप्पल राजधानी एक गुगल माइक्रोसफ्ट
ह्याशिंग गणित

यस समस्यामा, हामीलाई एक पूर्णा .्कन दिइन्छ, एन। लक्ष्य N भन्दा कम संख्याहरू कसरी प्राइम हुन्छन् भनेर गणना गर्नु हो। पूर्णांक गैर negativeणात्मकको लागि सीमित छ।

उदाहरणका

7
3
10
4

स्पष्टीकरण

१० भन्दा कम प्राइमहरू २,,, and र are हो। त्यसो भए, गणना 10 हो।

दृष्टिकोण (पशु बल)

सामान्य दृष्टिकोण N भन्दा कम प्रत्येक पूर्णाger्कको लागि जाँच गर्नु हो र यदि तिनीहरू प्राइम छन् भने परिणाम वृद्धि गर्दछ। उदाहरण को लागी, एन = १० लाई विचार गर्नुहोस्। अब, हामी २ मा N - १ देखि एक चक्र चलाउन सक्छौं कि कति दायरा भित्र यो पत्ता लगाउन। तर यस दृष्टिकोणलाई सम्पूर्ण दायरामा प्राइम चेक आवश्यक पर्दछ, [२, N - १]  तसर्थ, यो ढिलो छ।

हामी केहि अनुकूलन गर्न सक्छौं:

  1. २ बाहेक प्रत्येक प्राइम नम्बर बिजोर पूर्णाger्क हो। त्यसो भएपछि 2, हामी बिजोर पूर्णा .्क मात्र जाँच गर्न सक्छौं।
  2. हामी जाँच गर्न सक्दछौं कि यदि नम्बर प्राइममा छ भने O (√N) एल्गोरिथ्म सुधार गर्न समय।

यद्यपि हामीसँग अझै उत्तम दृष्टिकोण छ, यस लेखमा पछि छलफल गरिएको।

अल्गोरिदम

  1. यदि संख्या भन्दा कम छ भने 3, फर्किनु 0, किनकि २ सबैभन्दा सानो प्राइम हो
  2. Numbers बाट सुरू गरेर सबै नम्बरहरू जाँच गरेर एउटा लूप चलाउनुहोस्
  3. नम्बर, N प्राथमिक हुन्छ यदि:
    • यो संग २ र बीचको प्रमुख कारकहरू .N
  4. यदि संख्या प्राइम हो, वृद्धि परिणाम
  5. परिणाम प्रिन्ट गर्नुहोस्

काउन्ट प्राइमहरू लेटकोड समाधानहरूको कार्यान्वयन

C ++ कार्यक्रम

#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 (१), स्थिर स्थिर मात्र स्थिर भ्यारीएबलको लागि प्रयोग गरिन्छ।

दृष्टिकोण (अनुकूलन विधि)

कुनै पनि प्राथमिक संख्यालाई विचार गर्नुहोस्, मानौं 5, त्यसो भए यो पक्का छ कि the को सबै गुणनहरू आफैं बाहेक अरू कुनै पनि चीज प्रधान हुदैन किनकि उनीहरूसँग prime हुनुपर्दछ। त्यस्तै गरी हामी सबै नम्बर N भन्दा कम र ठूलो भण्डार गर्न सक्छौं 0

यो Eratosthenes को Sieve N भन्दा कम प्राइमहरू फेला पार्न एक प्राचीन र दक्ष एल्गोरिथ्म हो O (N) आवंटन गर्न एन पर्याप्त सानो छ मेमोरीमा खाली ठाउँ। यसले पुन: मिश्रितको रूपमा चिन्ह लगाई सबै गैर-प्राइम नम्बरहरू हटाउँछ। सबै कम्पोजिटहरू चिनो लगाइए पछि, अंकहरू जुन मार्क नगरिएको हुन्छ ती प्राइम हुन्।

साथै, हामीले बुलियन भण्डार गर्न आवश्यक छ array कुनै नम्बर अंकित गरिएको छ वा छैन भनेर जाँच गर्न, जुन मेमोरी प्रयोगको लागि खाता हो। त्यसो भए यो एक केस हो जहाँ हामी ट्रेड मेमोरी बन्द गर्न समयमा सुधार गर्नुहोस्.

प्राइमहरूको लेटकोड समाधानहरू गणना गर्नुहोस्

अल्गोरिदम

  1. बुलियन एर्रे कायम राख्नुहोस् प्रधानमन्त्री को आकार बराबर N - १
  2. प्रधान [] कम्पोजिटहरूलाई चिन्ह लगाउन र अन्त्यमा प्राइम जाँच गर्न प्रयोग गरिन्छ
  3. हरेक पूर्णांकको रूपमा सुरु गर्नुहोस् साँचो। एल्गोरिथ्म सेट गर्दछ झूटा प्रत्येक गैर-प्राइम नम्बरमा
  4. लगातार पूर्णाgers्कको एक लूप चलाउनुहोस्, २ बाट सुरु गरी पूर्णांकको पहिलो बहुफल नभएसम्म N भन्दा कम:
    • प्रत्येक पूर्णांक x को लागी, यदि यसमा प्राइम [x] सत्य छ भने, यसको सबै बहु को रूपमा मार्क गर्नुहोस् झूटा
    • यहाँ प्रत्येक पूर्णांकको गुणाबाट सुरू हुन्छ x * x जस्तो कि x का अन्य गुणहरू पहिले नै चिन्ह हटाईनेछ।
  5. अन्तमा [२, N - १] दायरामा कति संख्याहरू छन् जाँच गर्नुहोस् साँचो प्राइम टेबलमा
  6. परिणाम प्रिन्ट गर्नुहोस्

काउन्ट प्राइमहरू लेटकोड समाधानहरूको कार्यान्वयन

C ++ कार्यक्रम

#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 + +)। श्रृंखलाको योग (१/२ + १/1 + १/2 + १/1 + +) को रूपमा प्रमाणित गर्न सकिन्छ लग (लग एन)

तसर्थ, T (N) = Nlog (लग एन)

ठाउँ जटिलता

O (N), हामी भण्डार गर्न एक ह्यास तालिका बनाउन को रूप मा एक संख्या प्रधान छ वा छैन भने।