پرائمز لیٹ کوڈ حل کی گنتی کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون ایپل کیپٹل ایک گوگل مائیکروسافٹ
ہیکنگ ریاضی

اس مسئلے میں ، ہمیں ایک عدد اعداد و شمار دیئے جاتے ہیں ، N. مقصد یہ ہے کہ گننے کے لئے کہ 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) (اوسطا taking اسی طرح لگتا ہے 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))۔ اس کو ثابت کیا جاسکتا ہے:

ہر عدد ، X کے ل we ، ہم اس کا ایک وقت گزارتے ہیں N / 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 +…) ثابت ہوسکتا ہے لاگ (logN)۔

لہذا، T (N) = Nlog (logN)

خلائی پیچیدگی

O (N)، جیسا کہ ہم ذخیرہ کرنے کے لئے ہیش ٹیبل تیار کرتے ہیں اگر نمبر عظمیٰ ہے یا نہیں۔