كونت برايمز ليت كود حلول


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون أجهزة آبل عاصمة واحدة جوجل Microsoft
تجزئة الرياضيات

في هذه المسألة ، لدينا عدد صحيح ، N. والهدف هو حساب كيف أن الأرقام الأقل من N ، هي أعداد أولية. العدد الصحيح مقيد ليكون غير سالب.

مثال

7
3
10
4

تفسير

الأعداد الأولية الأقل من 10 هي 2 و 3 و 5 و 7. لذا ، فإن العدد هو 4.

نهج (القوة الغاشمة)

تتمثل الطريقة العامة في التحقق من كل عدد صحيح أقل من N وزيادة النتيجة إذا كانت عددًا أوليًا. على سبيل المثال ، ضع في اعتبارك N = 10. الآن ، يمكننا إجراء فحص من 2 إلى N - 1 لمعرفة عدد الأعداد الأولية الموجودة في هذا النطاق. لكن هذا النهج يتطلب فحصًا أوليًا للنطاق بالكامل ، [2 ، ن - 1].  لذلك ، هذا بطيء.

يمكننا القيام ببعض التحسينات مثل:

  1. كل عدد أولي غير 2 هو عدد صحيح فردي. وبعد ذلك 2, يمكننا التحقق من الأعداد الصحيحة الفردية فقط.
  2. يمكننا التحقق مما إذا كان الرقم أوليًا أم لا يا (√N) حان الوقت لتحسين الخوارزمية.

ومع ذلك ، لا يزال لدينا نهج أفضل ، تمت مناقشته لاحقًا في هذه المقالة.

خوارزمية

  1. إذا كان الرقم أقل من 3، إرجاع 0, حيث أن 2 هي أصغر عدد أولي
  2. قم بتشغيل حلقة للتحقق من جميع الأرقام ، بدءًا من 3
  3. رقم ، N هو عدد أولي إذا:
    • لديها العوامل الأولية بين 2 و √N
  4. إذا كان الرقم أوليًا ، تكون نتيجة الزيادة
  5. اطبع النتيجة

تنفيذ حلول Count Primes Leetcode

برنامج 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

تحليل التعقيد لحلول الكونت Primes Leetcode

تعقيد الوقت

نحن ندير حلقة ل N / 2 مرات. في كل شيك ، يكون وقت التعقيد O (N / 2) (بمتوسط لا / 2) اقضى. إذن ، التعقيد الزمني لهذه الخوارزمية هو يا (نون).

تعقيد الفضاء

يا (1)، يتم استخدام مسافة ثابتة فقط للمتغيرات الثابتة.

النهج (الطريقة المثلى)

فكر في أي عدد أولي ، على سبيل المثال 5, إذن فمن المؤكد أن جميع مضاعفات العدد 5 ، بخلاف نفسها ، لا يمكن أن تكون أبدًا عددًا أوليًا حيث سيكون لها 5 كأحد عواملها الأولية. وبالمثل ، يمكننا تخزين جميع الأرقام الأصغر من N وأكبر من 0

إن منخل إراتوستينس هي خوارزمية قديمة وفعالة للعثور على الأعداد الأولية أقل من N عندما N صغير بما يكفي لتخصيص O (N) مساحة في الذاكرة. إنه يزيل بشكل متكرر جميع الأعداد غير الأولية عن طريق تمييزها كمركبة. بعد وضع علامة على جميع المركبات ، فإن الأرقام غير المميزة هي أعداد أولية.

أيضًا ، نحتاج إلى تخزين قيمة منطقية مجموعة للتحقق مما إذا تم تمييز أي رقم أم لا ، أي حسابات لاستخدام الذاكرة. إذن ، هذه حالة نحن فيها ذاكرة التجارة قبالة إلى تحسن في الوقت المناسب.

كونت برايمز ليت كود حلول

خوارزمية

  1. الحفاظ على مجموعة منطقية رئيسي بحجم يساوي ن - 1
  2. رئيس [] يستخدم لتمييز المواد المركبة والتحقق من الأعداد الأولية في النهاية
  3. بدء رئيس الوزراء من كل عدد صحيح كما صحيح. مجموعات الخوارزمية زائف لكل عدد غير أولي
  4. قم بتشغيل حلقة من الأعداد الصحيحة المتتالية ، بدءًا من 2 حتى يصبح المضاعف الأول للعدد الصحيح أقل من N:
    • لكل عدد صحيح x ، إذا كان عدد أولي [x] صحيحًا ، ضع علامة على كل مضاعفاته زائف
    • يبدأ مضاعف كل عدد صحيح من س * س لأن جميع مضاعفات x الأخرى ستكون بالفعل بدون علامة.
  5. أخيرًا تحقق من عدد الأرقام الموجودة في النطاق [2 ، N - 1] صحيح في الجدول الرئيسي
  6. اطبع النتيجة

تنفيذ حلول Count Primes Leetcode

برنامج 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

تحليل التعقيد لحلول الكونت Primes Leetcode

تعقيد الوقت

تعقيد الخوارزمية O (Nlog (logN)). يمكن إثبات ذلك على النحو التالي:

نقضي وقتًا لكل عدد صحيح ، X ، غير متاح القضاء على كل مضاعفاته.

إذن ، إجمالي الوقت المستغرق هو: N / 2 + N / 3 + N / 5 + N / 7 + ……

أخذ N كما هو شائع ، T (N) = N (1/2 + 1/3 + 1/5 + 1/7 + ...). مجموع السلاسل (1/2 + 1/3 + 1/5 + 1/7 + ...) يمكن إثباته على أنه تسجيل الدخول (تسجيل ن).

ولذلك، T (N) = Nlog (تسجيل N)

تعقيد الفضاء

على)، حيث نقوم بإنشاء جدول تجزئة لتخزينه إذا كان الرقم أوليًا أم لا.